4 6 3 *** *B* *B* *H* *H* *** 4 4 **** *BB* *HH* **** 4 4 **** *BH* *HB* **** 5 6 ****** *.BB** *.H*H* *..*.* ******
3 1 2 Sorry , sir , my poor program fails to get an answer.
#include<stdio.h> #include<string.h> #include<iostream> #include<queue> using namespace std; int n,m,vis[25][25][25][25],sx[2],sy[2]; char map[25][25]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; struct s { int x[2],y[2],step,b[2],h[2]; //friend bool operator <(s a,s b) //{ // return a.step>b.step; //} }a,temp; int bfs() { memset(vis,0,sizeof(vis)); a.x[0]=sx[0],a.x[1]=sx[1]; a.y[0]=sy[0],a.y[1]=sy[1]; a.b[0]=a.b[1]=a.h[0]=a.h[1]=0; vis[sx[0]][sy[0]][sx[1]][sy[1]]=1; a.step=0; //priority_queue<struct s>q; queue<struct s>q; q.push(a); while(!q.empty()) { int i,j; //a=q.top(); a=q.front(); q.pop(); for(i=0;i<4;i++) { temp=a; for(j=0;j<2;j++) { if(temp.b[j]) continue; temp.x[j]=a.x[j]+dx[i]; temp.y[j]=a.y[j]+dy[i]; if(map[temp.x[j]][temp.y[j]]=='*') { temp.x[j]=a.x[j]; temp.y[j]=a.y[j]; } } if(vis[temp.x[0]][temp.y[0]][temp.x[1]][temp.y[1]]) continue; if(temp.x[0]==temp.x[1]&&temp.y[0]==temp.y[1]&&temp.b[0]+temp.b[1]==0) continue; vis[temp.x[0]][temp.y[0]][temp.x[1]][temp.y[1]]=1; temp.step=a.step+1; int flag=1; for(j=0;j<2;j++) { int now=map[temp.x[j]][temp.y[j]]; if(now<2&&!temp.h[now]) { temp.h[now]=1; temp.b[j]=1; } if(!temp.b[j]) flag=0; } if(flag) return temp.step; q.push(temp); } } return -1; } int main() { int t; scanf("%d",&t); while(t--) { int i,j; scanf("%d%d",&n,&m); int cnt=0,cot=0; for(i=0;i<n;i++) { scanf("%s",map[i]); for(j=0;j<m;j++) { if(map[i][j]=='H') { map[i][j]=cnt++; } if(map[i][j]=='B') { sx[cot]=i; sy[cot]=j; cot++; } } } int ans=bfs(); if(ans==-1) { printf("Sorry , sir , my poor program fails to get an answer.\n"); } else printf("%d\n",ans); } }
原文:http://blog.csdn.net/yu_ch_sh/article/details/44783581