BFS。。。
#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int map[1010][1010];
char str[1010][1010];
int n,m;
struct node
{
int x,y,step;
friend bool operator<(const node &a,const node &b)
{
return a.step>b.step;
}
}s,t;
int bfs()
{
priority_queue<node>Q;
node q,p;
int i,x,y,step,xx,yy;
Q.push(s);
map[s.x][s.y]=0;
while(!Q.empty())
{
q=Q.top();
Q.pop();
x=q.x;
y=q.y;
step=q.step;
if(x==t.x&&y==t.y)
return step;
for(i=0;i<4;i++)
{
p.x=xx=x+dir[i][0];
p.y=yy=y+dir[i][1];
if(xx<0||xx>=n||yy<0||yy>=m)
continue;
if(str[xx][yy]=='X')
p.step=step;//当遇到'X'时，不费时间
else
p.step=step+1;//当遇到‘.’
if(map[xx][yy]==-1||map[xx][yy]>step)
{
map[xx][yy]=step;
Q.push(p);
}
}
}
}
int main()
{
int i;
while(scanf("%d%d",&n,&m),n+m)
{
memset(map,-1,sizeof(map));
for(i=0;i<n;i++)
scanf("%s",str[i]);
scanf("%d%d",&s.x,&s.y);
scanf("%d%d",&t.x,&t.y);
s.x--;s.y--;s.step=0;
t.x--;t.y--;
printf("%d\n",bfs());
}
return 0;
}