Tempter of the Bone
http://acm.hdu.edu.cn/showproblem.php?pid=1010
#include <stdio.h>
#include <stdlib.h>
char map[][];
int dx[]={,,-,};
int dy[]={,,,-};
bool flag;
int n,m,xd,yd,t; void DFS(int x,int y,int t)
{
if(t==) //到时间了符合条件flag=true再退出，不符合条件直接退出。
{
if(x==xd&&y==yd)
flag=true;
return;
}
int temp=abs(x-xd)+abs(y-yd)-t;
if(temp>||temp&) //temp&1相当于temp%2，但是temp%2会超时，位运算比较快
return; //奇偶性剪枝+最小步数大于时间剪枝
if(flag)
return; //找到解后还有部分在继续搜索，这句是为了让其它搜索停止
int i;
int next_x,next_y;
for(i=;i<;i++)
{
next_x=x+dx[i];
next_y=y+dy[i];
if(next_x>=&&next_x<=m&&next_y>=&&next_y<=n&&map[next_y][next_x]!='X')
{
map[next_y][next_x]='X';
DFS(next_x,next_y,t-);
map[next_y][next_x]='.'; //回溯,如果搜不到D，还要恢复成原来的路径
}
}
} int main()
{
int i,j;
int x,y;
while(scanf("%d%d%d",&n,&m,&t)!=EOF)
{
if(n==&&m==&&t==)
break;
int wall=;
for(i=;i<=n;i++)
{
scanf("%s",map[i]+); //尽量用%s， %c容易出错
for(j=;j<=m;j++)
{
if(map[i][j]=='S')
{
x=j;
y=i;
}
if(map[i][j]=='D')
{
xd=j;
yd=i;
}
if(map[i][j]=='X')
wall++;
}
}
if(n*m-wall<=t) //可以走的格子比时间少，直接剪掉
printf("NO\n");
else
{
flag=false;
map[y][x]='X';
DFS(x,y,t);
if(flag)
printf("YES\n");
else
printf("NO\n");
} }
return ;
}
深度优先搜索(DFS)：解决迷宫问题（比如：能否逃离迷宫，只要判断能不能）
递归式基本框架：（不同的深搜代码千变万化）
void dfs(int si,int sj,int t) //si,sj为起始位置X行Y列坐标
{
int i;
if(si==di&&sj==dj&&t>=) // di,dj为目标位置，t为剩余时间，k为标记符号，可以就k=1
k=; // 能否在t时间内移动到坐标(di，dj)位置（逃离迷宫）？
if(si>=n||si<||sj>=m||sj<)
return; //防止走到地图外面去
if(k)
return; //终止条件，找到能出去的方法就直接return，不执行下面语句
for(i=;i<;i++) //dir[4][2]={1,0,0,1,-1,0,0,-1} 表示方向 ：上下左右
{
if(map[si+dir[i][]][sj+dir[i][]]!='X')
{
map[si+dir[i][]][sj+dir[i][]]='X'; //把走过的地方标记成 X，防止又往回走，
//（走来走去就死循环啦！）
dfs(si+dir[i][],sj+dir[i][],t-); // 递归，进一步搜索下去
map[si+dir[i][]][sj+dir[i][]]='.'; //用回溯法，如果上面的深搜失败，就把图还原到原来的状态
}
}
}
广度优先搜索(BFS)：适用解决最优解问题 （如:用时最少;代价最优;）
核心代码框架：
while(队列不为空)
{
node temp=Q.front();
//从该结点状态转移到其他状态
for(int i=;i<;i++) //int go[4][2] = {1,0,-1,0,0,1,0,-1}; 上下左右
{
int x=temp.x+go[i][];
int y=temp.y+go[i][];
int t=temp.t+;
//有选择的选择未出现过的状态入队 (用到哈希法，不明白的就百度一下 hash 吧)
if(hash[x][y]==false&&该点可行的条件)
{
if(x==dx&&y==dy) // 判断该状态是否为目的状态
return t;
hash[x][y]=true;
Q.push(newnode(x,y,t));
}
}
Q.pop(); // 弹出队列头结点
}