又贡献了n个TL……先用纯DFS写的，TL，然后无论怎嘛剪枝都是TL……然后加了一个record来记录已走过的地方的最短时间， 通过record来剪枝……终于AC了……这个也可以用BFS+优先级队列来做的！
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int n, m;
int visit[201][201];
int record[201][201];
int move[4][2]={{1,0},{ -1,0},{0,1},{0,-1}};
int t=99999;
void DFS(int sx, int sy, int ex, int ey, int time)
{
if( sx==ex&&sy==ey)
{
if (t>time) t=time;
return;
}
if( time+abs(ex-sx)+abs(ey-sy)>=t) return;//剪枝:话说这个剪枝无作用；
int i,j, tempx, tempy, Ttime, Tvisit;
for(i=0; i<4; i++)
{
tempx=sx+move[i][0];
tempy=sy+move[i][1];
if(tempx>=0&&tempx<=m && tempy>=0&&tempy<=n && visit[tempy][tempx] )
{
Tvisit=visit[tempy][tempx];
if(time+Tvisit>t) break;//剪枝:话说这个剪枝也无作用……
//记忆化搜索：当某一处已经走过，并且再次走到这个地方时所用时间大于以前所用的，则无需再走
//否者，就继续
if(record[tempy][tempx]==-1 || record[tempy][tempx]>time+Tvisit)
{
record[tempy][tempx]=time+Tvisit;
visit[tempy][tempx]=0;
//有guard的地方走一步需要时间为2,有路的地方走一步需要1
// 有guard的地方visit为2 ,有路的地方visit为1
DFS(tempx, tempy, ex, ey, time+Tvisit);
visit[tempy][tempx]=Tvisit;
}
}
}
}
int main()
{
char map[201];
int startX, startY, endX, endY, time, i, j;
while( scanf("%d %d",&n,&m)!=EOF )
{
t=99999;
memset(visit, 0, sizeof(visit) );
for(i=0; i<n; i++)
{
scanf("%s",map);
for(j=0; j<m; j++)
{
record[i][j]=-1;
if(map[j]=='#')//没有路的地方，标记为0
visit[i][j]=0;
else if(map[j]=='r')
{
startX=j;startY=i;
visit[i][j]=1;
}
else if( map[j]=='a')
{
endX=j;endY=i;
visit[i][j]=1;
}
else if(map[j]=='x')//有guard的地方标记为2
visit[i][j]=2;
else visit[i][j]=1;//有路的地方标记为1
}
}
DFS(startX, startY, endX, endY, 0);
if(t==99999) printf("Poor ANGEL has to stay in the prison all his life.\n");
else printf("%d\n", t);
}
}
附上我的TL代码……
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int n, m, startX, startY, endX, endY,;
int visit[201][201];
int move[4][2]={{1,0},{ -1,0},{0,1},{0,-1}};
int t=99999;
void DFS(int sx, int sy, int time)
{
if( sx==endX&&sy==endY)
{
if (t>time) t=time;
return;
}
if( time+abs(endX-tempx)+abs(endY-tempy)>=t) return;//剪枝1；
int i,j, tempx, tempy, Ttime, Tvisit;
for(i=0; i<4; i++)
{
tempx=sx+move[i][0];
tempy=sy+move[i][1];
if(tempx>=0&&tempx<=m && tempy>=0&&tempy<=n && visit[tempy][tempx])
{
Tvisit=visit[tempy][tempx];
if(time+Tvisit>=t) break;//剪枝1
visit[tempy][tempx]=0;
//有guard的地方走一步需要时间为2,有路的地方走一步需要1
// 有guard的地方visit为2 ,有路的地方visit为1
DFS(tempx, tempy, time+Tvisit);
visit[tempy][tempx]=Tvisit;
}
}
}
int main()
{
char map[201];
int time, i, j;
while( scanf("%d %d",&n,&m)!=EOF )
{
t=99999;
memset(visit, 0, sizeof(visit) );
getchar();
for(i=0; i<n; i++)
{
gets(map);
for(j=0; j<m; j++)
{
if(map[j]=='#')//没有路的地方，标记为0
visit[i][j]=0;
else if(map[j]=='r')
{
startX=j;startY=i;
}
else if( map[j]=='a')
{
endX=j;endY=i;
visit[i][j]=1;
}
else if(map[j]=='x')//有guard的地方标记为2
visit[i][j]=2;
else visit[i][j]=1;//有路的地方标记为1
}
}
DFS(startX, startY, 0);
if(t==99999) printf("Poor ANGEL has to stay in the prison all his life.\n");
else printf("%d\n", t);
}
}