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