题意：二维矩阵，，狱警从外面到里面去放两个犯人，问中途需要开的门的最小的次数。
分析：
这题从外面进去，那么只要是矩阵边缘可走的点（除了墙壁的点）都可作为起点，还有两个终点，所以直接枚举起点再搜索是不可行的。这题的做法是用三次bfs，分别求得从外面到每一个可走点的最小距离（开门次数）、两个犯人到每个可走点的最小距离，然后遍历一遍矩阵，把三个距离加起来，更新答案即可。求矩阵外面到矩阵里的最小距离是这么处理的：在输入的矩阵外面加上一圈可走点，然后从(0,0)的位置开始bfs即可（这样处理还有一个原因是最优解的交点可能不在输入矩阵的里面，而在外面）。
因为这里的最小距离不是走的步数而是开门次数，所以bfs要用优先队列，不然就会WA.
代码：
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<queue>#define INF 1000000007using namespace std;int t,n,m;char a[200][200];int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};int vis[200][200];int dis[4][200][200];struct node{int x,y;node(int x,int y):x(x),y(y){};};struct qnode{int x,y;int d;qnode(int x,int y,int d):x(x),y(y),d(d){}friend bool operator<(const qnode &a,const qnode &b){return a.d>b.d;}};priority_queue<qnode> q;void bfs(int x,int y,int p){memset(vis,0,sizeof(vis));while(!q.empty()) q.pop();qnode tp=qnode(x,y,0);q.push(tp);vis[x][y]=1;while(!q.empty()){qnode tmp=q.top();q.pop();for(int i=0;i<4;i++){int dx=tmp.x+d[i][0];int dy=tmp.y+d[i][1];if(dx>=0&&dx<=n+1&&dy>=0&&dy<=m+1&&a[dx][dy]!='*'&&!vis[dx][dy]){vis[dx][dy]=1;if(a[dx][dy]=='#') dis[p][dx][dy]=dis[p][tmp.x][tmp.y]+1;else dis[p][dx][dy]=dis[p][tmp.x][tmp.y];qnode tmp1=qnode(dx,dy,dis[p][dx][dy]);q.push(tmp1);}}}}int main(){scanf("%d",&t);while(t–){scanf("%d%d",&n,&m);int ex1=-1,ey1=-1,ex2,ey2;for(int i=0;i<=n+1;i++) a[i][0]='.',a[i][m+1]='.';for(int i=0;i<=m+1;i++) a[0][i]='.',a[n+1][i]='.';for(int i=1;i<=n;i++) scanf("%s",a[i]+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='$'){if(ex1==-1) ex1=i,ey1=j;else ex2=i,ey2=j;}}}memset(dis,0,sizeof(dis));bfs(0,0,0);bfs(ex1,ey1,1);//for(int i=0;i<n;i++){//for(int j=0;j<m;j++) cout<<dis[1][i][j];cout<<endl;}bfs(ex2,ey2,2);int ans=INF;for(int i=0;i<=n+1;i++){for(int j=0;j<=m+1;j++){if(a[i][j]=='.'||a[i][j]=='$'){int sum=0;for(int k=0;k<3;k++){sum+=dis[k][i][j];}ans=min(ans,sum);}else if(a[i][j]=='#'){int sum=0;for(int k=0;k<3;k++){sum+=dis[k][i][j];}ans=min(ans,sum-2);}}}cout<<ans<<endl;}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
不做任何解释。没有人明白，
