Battle City
Input
Output
Sample Input
3 4 YBEB EERE SSTE 0 0
Sample Output
8
又是一道BFS+优先队列的题，和之前的WAR CHESS类似，但判断条件较少。这次主要是想作个比较，用暴力DFS跑一边，果断TLE。。BFS+优先队列只遍历最少步数之内的点一次，时间效率快很多
dfs length 861 time 1s+
bfs length 1469 time 0.016s memory 1m
| Status | Time Limit Exceeded |
|---|---|
| Length | 861 |
| Lang | G++ |
| Submitted | 2017-07-22 22:22:12 |
| Shared | |
| RemoteRunId | 17284030 |
| Status | Accepted |
|---|---|
| Time | 16ms |
| Memory | 1028kB |
| Length | 1469 |
| Lang | G++ |
| Submitted | 2017-07-22 22:22:58 |
| Shared | |
| RemoteRunId | 17284040 |
#include<stdio.h>
#include<string.h> char a[305][305]; int b[305][305]; int n,m,f,bx,by,min; void dfs(int x,int y,int s) { if(x<0||y<0||x>=n||y>=m) return; if(b[x][y]==1) return; if(a[x][y]==‘T‘){ f=1; if(s<min) min=s; return; } else if(a[x][y]==‘S‘){ b[x][y]=1; return; } else if(a[x][y]==‘R‘){ b[x][y]=1; return; } else if(a[x][y]==‘B‘){ s++; } b[x][y]=1;dfs(x+1,y,s+1);b[x][y]=0; b[x][y]=1;dfs(x,y+1,s+1);b[x][y]=0; b[x][y]=1;dfs(x-1,y,s+1);b[x][y]=0; b[x][y]=1;dfs(x,y-1,s+1);b[x][y]=0; } int main() { int i,j; while(scanf("%d%d",&n,&m)&&!(n==0&&m==0)){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(i=0;i<n;i++){ scanf("%s",a[i]); for(j=0;j<m;j++){ if(a[i][j]==‘Y‘){ bx=i;by=j; } } } f=0; min=200000; dfs(bx,by,0); if(f==1) printf("%d\n",min); else printf("-1\n"); } return 0; }
#include<stdio.h> #include<string.h> #include<queue> using namespace std; char a[305][305]; int b[305][305]; int t[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int n,m,bx,by; struct Node{ int x,y,s; friend bool operator<(Node a,Node b) { return a.s>b.s; } }node; void bfs() { int i,f=0,tx,ty; priority_queue<Node> q; node.x=bx; node.y=by; node.s=0; b[bx][by]=1; q.push(node); while(q.size()){ for(i=0;i<4;i++){ tx=q.top().x+t[i][0]; ty=q.top().y+t[i][1]; if(tx<0||ty<0||tx>=n||ty>=m) continue; if(b[tx][ty]==1) continue; b[tx][ty]=1; if(a[tx][ty]==‘T‘){ printf("%d\n",q.top().s+1); f=1; return; } else if(a[tx][ty]==‘S‘){ b[tx][ty]=1; continue; } else if(a[tx][ty]==‘R‘){ b[tx][ty]=1; continue; } else if(a[tx][ty]==‘B‘){ node.x=tx; node.y=ty; node.s=q.top().s+2; b[tx][ty]=1; q.push(node); } else if(a[tx][ty]==‘E‘){ node.x=tx; node.y=ty; node.s=q.top().s+1; b[tx][ty]=1; q.push(node); } } q.pop(); } if(f==0) printf("-1\n"); } int main() { int i,j; while(scanf("%d%d",&n,&m)&&!(n==0&&m==0)){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(i=0;i<n;i++){ scanf("%s",a[i]); for(j=0;j<m;j++){ if(a[i][j]==‘Y‘){ bx=i;by=j; } } } bfs(); } return 0; }
原文：http://www.cnblogs.com/yzm10/p/7223155.html