http://acm.hdu.edu.cn/showproblem.php?pid=2822
给定起点和终点,问从起点到终点需要挖几次只有从# 到 .或者从. 到 . 才需要挖一次。
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = ;
int n,m;
int sx,sy,ex,ey;
char maze[maxn][maxn];
int vis[maxn][maxn];
int dir[][]={-,,,,,,,-};
struct point
{
int x,y,step;
char z;
bool operator < (const point a) const
{
return step>a.step;
}
}; int bfs()
{
// printf("%d %d\n",a,b);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
vis[i][j]=<<;
priority_queue<point>que;
point s;
s.x=sx;s.y=sy;s.step=;s.z='X';
que.push(s);
vis[s.x][s.y]=;
while(!que.empty())
{
point e=que.top();que.pop();
//printf("%d %d %d\n",e.x,e.y,e.step);
if(e.x==ex&&e.y==ey) return e.step;
for(int i=;i<;i++)
{
s=e;
s.x=e.x+dir[i][];
s.y=e.y+dir[i][];
if(s.x>=&&s.x<n&&s.y>=&&s.y<m)
{
if(maze[s.x][s.y]=='X') s.step=e.step;
else if(maze[s.x][s.y]=='.') s.step=e.step+;
if(s.step<vis[s.x][s.y])
{
vis[s.x][s.y]=s.step;
que.push(s);
}
}
}
}
} int main()
{
//freopen("a.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
if(n==&&m==) break;
for(int i=;i<n;i++)
{
scanf("%s",maze[i]);
// printf("%s\n",maze[i]);
}
scanf("%d %d",&sx,&sy);
scanf("%d %d",&ex,&ey);
//printf("%d%d%d%d\n",sx,sy,ex,ey);
sx--,sy--,ex--,ey--;
printf("%d\n",bfs());
}
return ;
}