题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2822
题目大意:X消耗0,.消耗1, 求起点到终点最短消耗
解题思路:
每层BFS的结点,优先级不同,应该先搜cost小的。直接退化为最短路问题。
优先队列优化。
卡输入姿势。如果O(n^2)逐个读的话会T掉。要用字符串读一行。
#include "cstdio"
#include "queue"
#include "cstring"
using namespace std;
#define maxn 1005
bool vis[maxn][maxn];
char map[maxn][maxn];
int n,m,dir[][]={-,,,,,-,,},sx,sy,ex,ey;
struct status
{
int x,y,dep;
status(int x,int y,int dep):x(x),y(y),dep(dep) {}
bool operator < (const status &a) const {return dep>a.dep;}
};
int bfs()
{
priority_queue<status> Q;Q.push(status(sx,sy,));
vis[sx][sy]=true;
while(!Q.empty())
{
status t=Q.top();Q.pop();
for(int s=;s<;s++)
{
int X=t.x+dir[s][],Y=t.y+dir[s][];
if(X<||X>n||Y<||Y>m||vis[X][Y]) continue;
int cost=map[X][Y]=='.'?:;
if(X==ex&&Y==ey) return t.dep+cost;
vis[X][Y]=true;
Q.push(status(X,Y,t.dep+cost));
}
}
return -;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&m)&&n)
{
memset(vis,,sizeof(vis));
for (int i=;i<=n;i++) scanf("%s",map[i]+);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
int ans=bfs();
printf("%d\n",ans);
}
}