开始做这题时先是想了几天，想出来方法了（没去写），之后认真看了一下，照以前的思路写了一下，有一些样例过不了，标记出现问题，想了好久的标记还是没想出来一种好的标记方法，最后还是忍不住问了度娘一下，一看……
我怎么没想出来呢！！！
做题总结：首先有想法就应该去实现，不要整天想而不去实现，其次是想不出来再想（坚持不住的时候，再坚持一下！）。
代码：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std ;
int n,m,rx,ry ;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
int _dx[4]={-1,1,0,0},_dy[4]={0,0,-1,1} ;//反方向 这不错！
int vis[10][10],g[10][10],vix[10][10][10][10] ;
struct zhang
{
int x,y,cx,cy,bu ;
} ;
struct node
{
int x,y ;
} ;
int _bfs(int x,int y,int ax,int ay)//看是否能搜索到人
{
queue<node>q ;
node current,next ;
memset(vis,0,sizeof(vis)) ;
current.x=x ;
current.y=y ;
q.push(current) ;
while(!q.empty())
{
current=q.front() ;
q.pop() ;
if(current.x==ax&¤t.y==ay)
return 1 ;
for(int i=0;i<4;i++)
{
next.x=current.x+dx[i] ;
next.y=current.y+dy[i] ;
if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&g[next.x][next.y]!=1&&!vis[next.x][next.y])
{
vis[next.x][next.y]=1 ;
q.push(next) ;
}
}
}
return 0 ;
}
int bfs(int x,int y,int ax,int ay)
{
queue<zhang>q ;
zhang current,next ;
int fm ;
memset(vix,0,sizeof(vix)) ;
current.x=x ;
current.y=y ;
current.cx=ax ;
current.cy=ay ;
vix[x][y][ax][ay]=1 ;//考虑到这点很重要，可以避免重复走一样的
current.bu=0 ;
q.push(current) ;
while(!q.empty())
{
current=q.front() ;
q.pop() ;
if(current.x==rx&¤t.y==ry)
return current.bu ;
for(int i=0;i<4;i++)
{
next.x=current.x+dx[i] ;
next.y=current.y+dy[i] ;
next.cx=current.x+_dx[i] ;
next.cy=current.y+_dy[i] ;
int z=g[current.x][current.y] ;
fm=0 ;
if(next.cx>=0&&next.cy>=0&&next.cx<n&&next.cy<m&&g[next.cx][next.cy]!=1)
{
g[current.x][current.y]=1 ;
fm=_bfs(next.cx,next.cy,current.cx,current.cy) ;
g[current.x][current.y]=z ;
}
if(!vix[next.x][next.y][next.cx][next.cy]&&next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&g[next.x][next.y]!=1&&fm)
{
vix[next.x][next.y][next.cx][next.cy]=1 ;
next.bu=current.bu+1 ;
q.push(next) ;
}
}
}
return -1 ;
}
int main()
{
int T,i,j,ex,ey,qx,qy ;
scanf("%d",&T) ;
while(T--)
{
scanf("%d%d",&n,&m) ;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%d",&g[i][j]) ;
if(g[i][j]==2)
{
ex=i ;
ey=j ;
}
else if(g[i][j]==3)
{
rx=i ;
ry=j ;
}
else if(g[i][j]==4)
{
qx=i ;
qy=j ;
}
}
printf("%d\n",bfs(ex,ey,qx,qy)) ;
}
return 0 ;
}