dfs + 回溯 +剪枝_dfs+回溯+减枝

hdu  1010

Tempter of the Bone

  
  

   
   4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
  
  

  
  

   
   NO
YES
  
  

题目大意：这道题就是讲有一只狗要吃骨头，结果进入了一个迷宫陷阱，迷宫里每走过一个地板费时一秒，该地板就会在下一秒塌陷，所以你不能在该地板上逗留。迷宫里面有一个门，只能在特定的某一秒才能打开，让狗逃出去。现在题目告诉你迷宫的大小和门打开的时间，问你狗可不可以逃出去，可以就输出YES,否则NO。
解题思路：这道题，要用到剪枝搜索来做，否则会超时。剪掉的条件是，如果可走地板数目小于给定的时间，绝对不可能得救。还有就是狗走到门的时间必须和题目给定的时间是同奇同偶的，否则也不能在指定的那秒到达门，也不可能得救，剪掉这两种情况后。就用深度搜索来做。从起点出发，深搜周围的路，走过的路就标记为不可走，一直搜索下去，如果搜索失败就回溯，恢复原数据，把可能的路都搜索一遍过去，看看是否有可行方案。
关于剪枝,没有剪枝的搜索不太可能,一个是奇偶剪枝,一个是路径剪枝
奇偶剪枝:
把矩阵标记成如下形式:
0,1,0,1,0
1,0,1,0,1
0,1,0,1,0
1,0,1,0,1
很明显,如果起点在0 而终点在1 那显然 要经过奇数步才能从起点走到终点,依次类推,奇偶相同的偶数步,奇偶不同的奇数步
在读入数据的时候就可以判断,并且做剪枝,当然做的时候并不要求把整个矩阵0,1刷一遍,读入的时候起点记为(Si,Sj) 终点记为(Di,Dj) 判断(Si+Sj) 和 (Di+Dj) 的奇偶性就可以了
路径剪枝:
矩阵的大小是N*M 墙的数量记为num 如果能走的路的数量 N*M - num 小于时间T,就是说走完也不能到总的时间的,这显然是错误的,可以直接跳出了
剪枝3:就是记录当前点到终点的最短路,如果小于剩余的时间的话,就跳出

什么也不加很裸很裸地 TLE 代码：

#include <iostream>
#include <cstring>
using namespace std;
int n,m,T;
char map[10][10],vis[10][10];
bool survive;
int dir[][2]= {{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y,int tim)
{
//cout<<x<<" "<<y<<" "<<tim<<endl;
if(tim>T||survive) return;
if(map[x][y]=='D'&&tim==T)
{
survive=1;
return;
}
vis[x][y]=1;
for(int i=0; i<4&&!survive; i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx<0||nx>=n) continue;
if(ny<0||ny>=m) continue;
if(vis[nx][ny]||map[nx][ny]=='X') continue;
//cout<<nx<<" "<<ny<<endl;
dfs(nx,ny,tim+1);
}
vis[x][y]=0;
}
int main()
{
int sx,sy;
while(cin>>n>>m>>T&&(n||m||T))
{
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>map[i][j];
if(map[i][j]=='S') sx=i,sy=j;
}
memset(vis,0,sizeof(vis));
survive=0;
// cout<<sx<<" "<<sy<<endl;
dfs(sx,sy,0);
if(survive) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
int n,m,T;
char map[10][10],vis[10][10];
bool survive;
int dir[][2]= {{0,1},{0,-1},{1,0},{-1,0}};
int sx,sy,ex,ey;
int abs(int x)
{
return x<0?-x:x;
}
void dfs(int x,int y,int tim)
{
//if(f[x][y][tim]!=-1) return;
if(tim>T||survive) return;
if(map[x][y]=='D'&&tim==T)
{
survive=1;
return;
}
if(abs(x-ex)+abs(y-ey)>T-tim) return;
vis[x][y]=1;
for(int i=0; i<4&&!survive; i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx<0||nx>=n) continue;
if(ny<0||ny>=m) continue;
if(vis[nx][ny]||map[nx][ny]=='X') continue;
//cout<<nx<<" "<<ny<<endl;
dfs(nx,ny,tim+1);
}
vis[x][y]=0;
}
int main()
{
while(cin>>n>>m>>T&&(n||m||T))
{
int num=0;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>map[i][j];
if(map[i][j]=='S') sx=i,sy=j;
if(map[i][j]=='D') ex=i,ey=j;
if(map[i][j]!='X') num++;
}
if(num-1<T) {cout<<"NO"<<endl; continue;}
memset(vis,0,sizeof(vis));
// memset(f,-1,sizeof(f));
survive=0;
if((sx+sy+ex+ey+T)%2==0)
dfs(sx,sy,0);
if(survive) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}