Description
小明最近喜欢玩一个游戏。给定一个n * m的棋盘,上面有两种格子#和@。游戏的规则很简单:给定一个起始位置和一个目标位置,小明每一步能向上,下,左,右四个方向移动一格。如果移动到同一类型的格子,则费用是0,否则费用是1。请编程计算从起始位置移动到目标位置的最小花费。
Input
输入文件有多组数据。
输入第一行包含两个整数n,m,分别表示棋盘的行数和列数。
输入接下来的n行,每一行有m个格子(使用#或者@表示)。
输入接下来一行有四个整数x1, y1, x2, y2,分别为起始位置和目标位置。
当输入n,m均为0时,表示输入结束。
Output
对于每组数据,输出从起始位置到目标位置的最小花费。每一组数据独占一行。
Sample Input
2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0
Sample Output
2
0
0
HINT
对于100%的数据满足:1 < = n, m <= 500。
Solution
跑最短路即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstdio> using namespace std; const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},N=505; int n,m,X1,Y1,X2,Y2,dis[N][N],x[N*N*2],y[N*N*2]; char s[N][N]; bool visit[N][N]; void SPFA() { for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) visit[i][j]=false,dis[i][j]=1<<29; int t=0,w=1;x[1]=X1;y[1]=Y1;visit[X1][Y1]=true;dis[X1][Y1]=0; while (t!=w) { t++; if (t>n*m*2) t=1; int ux=x[t],uy=y[t]; visit[ux][uy]=false; for (int i=0;i<=3;i++) { int vx=ux+dx[i],vy=uy+dy[i]; if (vx<0||vx>=n||vy<0||vy>=m) continue; if (dis[vx][vy]>dis[ux][uy]+(s[ux][uy]!=s[vx][vy])) { dis[vx][vy]=dis[ux][uy]+(s[ux][uy]!=s[vx][vy]); if (!visit[vx][vy]) { w++; if (w>n*m*2) w=1; x[w]=vx;y[w]=vy; visit[vx][vy]=true; } } } } printf("%d\n",dis[X2][Y2]); } int main() { while (true) { scanf("%d%d",&n,&m); if (n==0&&m==0) break; for (int i=0;i<n;i++) scanf("%s",s[i]); scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2); SPFA(); } return 0; } |