HDU_1010
这个题目由于block只能经过一次，那么我们在搜索的过程中就必须要记录各个block的状态了，而且这个题目跟最短的距离并无直接联系，如果使用bfs的话还必须要将所有的路径搜到不能走或者时间到T的时候，无论是空间还是时间上都耗费很大，所以我们选用好写的dfs就可以了。
此外这个题目还有一个预先初步判断初始状态是否可达，原理就像是把格子染成国际棋盘一样，dog在奇数的时间时只能走到某种颜色的格子内，而在偶数的时间时只能走到另一种颜色的格子内，所以如果终点和起点的曼哈顿距离模2的结果和T不一样的话，肯定是无解的。至于这个表达式怎么来的，我们分几种情况讨论一下就可以得到了。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 10
char b[MAXD];
int g[MAXD][MAXD], vis[MAXD][MAXD], sx, sy, tx, ty;
int N, M, T, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
void init()
{
int i, j, k;
memset(g, 0, sizeof(g));
for(i = 1; i <= N; i ++)
{
scanf("%s", b + 1);
for(j = 1; j <= M; j ++)
if(b[j] != 'X')
{
g[i][j] = 1;
if(b[j] == 'S')
sx = i, sy = j;
else if(b[j] == 'D')
tx = i, ty = j;
}
}
}
int dfs(int x, int y, int t)
{
if(t == 0)
{
if(x == tx && y == ty)
return 1;
return 0;
}
if(x == tx && y == ty)
return 0;
vis[x][y] = 1;
int i, newx, newy;
for(i = 0; i < 4; i ++)
{
newx = x + dx[i], newy = y + dy[i];
if(g[newx][newy] && !vis[newx][newy] && dfs(newx, newy, t - 1))
return 1;
}
vis[x][y] = 0;
return 0;
}
void solve()
{
memset(vis, 0, sizeof(vis));
if((abs(tx - sx) + abs(ty - sy)) % 2 == T % 2)
{
if(dfs(sx, sy, T))
printf("YES\n");
else
printf("NO\n");
}
else
printf("NO\n");
}
int main()
{
for(;;)
{
scanf("%d%d%d", &N, &M, &T);
if(!N && !M && !T)
break;
init();
solve();
}
return 0;
}