/*
简单的深搜,需要注意题意里一点,如果一开始就遇到墙壁,则不能往该方向移动
*/
#include<stdio.h>
#include<string.h>
#define MAX 50
int map[MAX][MAX];
int w,h,result;
int start_i,start_j,end_i,end_j;
int d[][2]={ {0,-1}
,{-1,0}
,{0,1}
,{1,0}
};
void dfs(int i,int j,int step)
{
int k,next_i,next_j;
if(step>=result)return;
step++;
for(k=0; k<4; ++k)
{
next_i = i+d[k][0];
next_j = j+d[k][1];
//You may throw it to any direction unless it is blocked immediately
//如果一开始就是墙壁则不能破开
if(next_i<0 || next_i>h || next_j<0 || next_j>w || map[next_i][next_j]==1)continue;
while(next_i>=0 && next_i<h && next_j>=0 && next_j<w && map[next_i][next_j]==0 )
{
next_i += d[k][0];
next_j += d[k][1];
}
if(next_i<0 || next_i>=h || next_j<0 || next_j>=w)continue;
if(map[next_i][next_j]==3)
{
if(step<result)result=step;
return;
}
if(map[next_i][next_j]==1)
{
map[next_i][next_j]=0;
dfs(next_i-d[k][0], next_j-d[k][1], step);
map[next_i][next_j]=1;
}
}
}
int main()
{
int i,j;
freopen("data","r",stdin);
while( scanf("%d %d",&w,&h),w!=0 && h!=0 )
{
memset(map,0,sizeof(map));
result = 11;
for(i=0; i<h; ++i)
{
for(j=0; j<w; ++j)
{
scanf("%d",&map[i][j]);
if( map[i][j]==2 )
{
start_i = i;
start_j = j;
map[i][j]=0;
}else if( map[i][j]==3 )
{
end_i = i;
end_j = j;
}
}
}
dfs(start_i,start_j,0);
if(result>10)printf("-1\n");
else printf("%d\n",result);
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1750462
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1703983
很详尽的讲述了简单的深搜,宽搜算法,另外还有剪枝策略,另外附加了poj上的题目举例分析。 (作者:东北师大计算机学院程文华)
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
NULL 博文链接:https://128kj.iteye.com/blog/1772172
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
用DFS深搜,你会发现时间复杂非常高,必然会超时(最大是300*300的图)。本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种方法来解决。第一种方法:改进过的BFS:有些节点需要耗费2个单位时间,要
1.16.17 pku3668_GameofLine_N个点最多确定多少互不平行的直线(poj3668) 99 1.16.18 求凸多边形直径 100 2.组合 102 2.1 组合公式 102 2.2 排列组合生成 102 2.3 生成gray码 104 2.4 置换(polya) 104 2.5 字典序...