思路：一开始以为是一道DFS，也很快就写好代码，发现编译后结果错误。发现题目给的第一组数据就不行了，又看了一下，发现我的代码不能实现最优路径，于是又自作聪明地将走过的路径标记掉，又运行了一下，发现第三组数据又不行了，原来我的代码在这组数据就不行了，这样才发现并不是标记掉就行的，有些数据不标记掉能够成功走出，反而标记掉就不能走出来。这时，就要判断了。想了一会，觉得应该用BFS。不过BFS一般要标记走过的点。顿时没了思路。最后，纠结地在网上查了资料。原来确实可以用BFS，只不过这里就不要标记了。只需判断，前一步走过的点，后来又走了一遍，显然后来走的时间耗费要比前面的多，这时就要考虑二个时刻的炸弹剩余爆炸时间。如果后面大于前面的。就表明后面的点可以扩展。最后，总结：自己对搜索毕竟还很不熟悉，且对其的变化知之甚微。自己应加强对搜索题的灵敏度，这样对各种变化就能够知道所以然了。
代码如下：#include <iostream>#include <queue>using namespace std;int str[9][9],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};int time[9][9];int N,M;int si,sj,ei,ej,flag;typedef struct{ int x,y; int pasttime,lefttime;}point;void bfs(){ point p1,p2; int i,j; queue<point> q; p1.x=si; p1.y=sj; p1.pasttime=0; p1.lefttime=6; for(i=0;i<9;i++) for(j=0;j<9;j++) time[i][j]=0; time[p1.x][p1.y]=6; q.push(p1); while(!q.empty()) { p1=q.front(); q.pop(); for(i=0;i<4;i++) { p2.x=p1.x+dir[i][0]; p2.y=p1.y+dir[i][1]; p2.lefttime=p1.lefttime; p2.pasttime=p1.pasttime; if(p2.x>=0&&p2.x<N&&p2.y>=0&&p2.y<M&&str[p2.x][p2.y]!=0) { p2.pasttime++; p2.lefttime--; if(p2.lefttime>0&&p2.x==ei&&p2.y==ej) { cout<<p2.pasttime<<endl; flag=1; return; } if(p2.lefttime>1&&str[p2.x][p2.y]==1) { if(p2.lefttime>time[p2.x][p2.y]) { time[p2.x][p2.y]=p2.lefttime; q.push(p2); } } else if(p2.lefttime>0&&str[p2.x][p2.y]==4) { p2.lefttime=6; if(p2.lefttime>time[p2.x][p2.y]) { time[p2.x][p2.y]=6; q.push(p2); } } } } } if(!flag) cout<<-1<<endl;
}int main(){ int i,j; int num; cin>>num; while(num--) { cin>>N>>M; for(i=0;i<N;i++) for(j=0;j<M;j++) { cin>>str[i][j]; if(str[i][j]==2) { si=i; sj=j; } if(str[i][j]==3) { ei=i; ej=j; } } flag=0; bfs(); } return 0;}
38232572011-04-15 19:20:43Accepted10720MS276K1576 BC++
