HDU1010 Tempter of the Bone

解题思路:相当经典的一题,回溯,具体细节处理见代码。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = ;
int vis[maxn][maxn], dir[][] = {, , -, , , , , -};
char mapp[maxn][maxn];
int n, m, t, flag, cnt, si, sj, di, dj; void DFS(int x, int y, int cnt)
{
if(x == di && y == dj) //如果走到终点
{
if(cnt == t) flag = ; //并且步数恰好等于时间,门正好打开。
return ; //不过是否走出去,都必须返回
}
if(cnt >= t) return ; //超过时间再继续走已经没有意义了。
if(mapp[x][y] == 'X') return ; //X的地方是不能走的。
vis[x][y] = ; //标记为已经走过
for(int i = ; i < ; i++) //四个方向搜索
{
int xx = x + dir[i][];
int yy = y + dir[i][]; //初始化时边界之外的地方都标记为X,所以此处包括边界的判断。
if(mapp[xx][yy] == 'X' || vis[xx][yy]) continue;
vis[xx][yy] = ; //标记为已走过
DFS(xx, yy, cnt + ); //搜索
vis[xx][yy] = ; //回溯
if(flag) return ; //这步至关重要,否则会TLE
}
return ;
} int main()
{
while(~scanf("%d %d %d", &n, &m, &t) && (n || m || t))
{
memset(vis, , sizeof(vis)); //全部标记为没有走过
memset(mapp, 'X', sizeof(mapp)); //边界之外也标记为X
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
scanf(" %c", &mapp[i][j]);
if(mapp[i][j] == 'S') si = i, sj = j;
if(mapp[i][j] == 'D') di = i, dj = j;
}
} //非常经典的剪枝,否者会TLE
//如果走到该点所用的最少步数都超过t,是不可能走到的。
//后面一个条件是奇偶判断的问题,需要好好思考
if(abs(si-di) + abs(sj-dj) > t || (si+sj+di+dj+t) % == )
{
printf("NO\n");
continue;
} flag = , cnt = ;
DFS(si, sj, );
if(flag) printf("YES\n"); //如果flag==1,则表明走出来了。
else printf("NO\n");
}
return ;
}
上一篇:java面试| 精选基础题(2)


下一篇:JAVA面试精选【Java算法与编程一】