题意:一个n*m(n,m<=50)的矩阵有一片连着的树林,Bessie要从起始位置出发绕林子一圈再回来,每次只能向横着、竖着或斜着走一步。问最少需多少步才能完成。

/*
如果我们用搜索来写的话,如果搜出的路径能够包围其中的一个点,那么就能包围森林,这样问题就被简化了。
我们任选一个点作为被包围点,在搜索时利用射线原理判断某这个点是否在多边形中(判断函数需要认真考虑)。
如果这条射线经过多边形奇数次,则在多边形内,否则不在。
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define N 60
using namespace std;
char map[N][N],ch[N];
int n,m,sx,sy,gx,gy,nx,ny,tx,ty,dp[N][N][];
int dx[]={-,,,,-,-,,};
int dy[]={,,-,,-,,-,};
struct node{int x,y,k;};
bool ok(){
if(tx==gx&&ty<gy){
if(nx<tx)return true;
}
else if(nx==gx&&ny<gy){
if(nx>tx)return true;
}
return false;
}
void bfs(){
memset(dp,-,sizeof(dp));
queue<node> q;
node u;u.x=sx;u.y=sy;u.k=;dp[sx][sy][]=;q.push(u);
while(!q.empty()){
u=q.front();q.pop();nx=u.x;ny=u.y;int nk=u.k,tk;
for(int i=;i<;i++){
tx=nx+dx[i];ty=ny+dy[i];tk=nk;
if(tx<||tx>n||ty<||ty>m||map[tx][ty]=='X')continue;
if(ok())tk^=;
if(dp[tx][ty][tk]==-){
dp[tx][ty][tk]=dp[nx][ny][u.k]+;
node v;v.x=tx;v.y=ty;v.k=tk;q.push(v);
}
}
}
printf("%d\n",dp[sx][sy][]);
}
int main(){
scanf("%d%d",&n,&m);
bool flag=false;
for(int i=;i<=n;i++){
scanf("%s",ch);
for(int j=;j<=m;j++){
map[i][j]=ch[j-];
if(map[i][j]=='*')sx=i,sy=j;
if(!flag&&map[i][j]=='X')flag=,gx=i,gy=j;
}
}
bfs();
return ;
}

最新文章

  1. [Top-Down Approach]Take Notes
  2. [delphi]极域学生端解除键盘鼠标锁定退出全屏广播-强制窗口化-源代码
  3. win系统下nodejs安装及环境配置
  4. Android DiskLruCache 硬盘缓存
  5. SQL中一种类似GUID值的函数实现
  6. IntelliJ IDEA 15开发Java Maven项目
  7. JS原型与原型链终极详解(转)
  8. Android----二维码开发
  9. Angularjs Scope 原型链
  10. Codeforces 360C Levko and Strings dp
  11. 华为S5700设置vlan,并绑定电脑的IP地址与mac地址。
  12. Centos 7 64位 minimal 最小化安装的系统中静默安装oracle 11g r2
  13. Py福利,基于uiautomatorviewer 的Python 自动化代码自动生成工具分享(jar已发布GitHub,欢迎Star)
  14. win32线程
  15. [2017BUAA软工助教]个人项目准备工作
  16. C#自定义按钮、自定义WinForm无边框窗体、自定义MessageBox窗体
  17. phpStorm 8.0.3 设置
  18. CSU 1948: 超级管理员(普通费用流&amp;&amp;zkw费用流)
  19. 介绍一个基于jQuery的Cookie操作插件
  20. AIX常用命令汇总(转)

热门文章

  1. AJPFX总结String类的特点
  2. 【转】Java中创建对象的5种方式
  3. checkbox:click事件触发span元素内容改变
  4. 一个Java编写的小玩意儿--脚本语言解释器(一)
  5. 使用代码编辑器Sublime Text 3进行前端开发及相关快捷键
  6. C++ new delete(一)
  7. 「 HDOJ P2227 」 Find the nondecreasing subsequences
  8. GO:interface
  9. Python:字体颜色
  10. 第三章:systemverilog文本值和数据类型