1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=510; int n,m,X1,Y1,X2,Y2,d[N][N]; char ss[N][N]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; struct node{int x,y;}; int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0)break; for(int i=1;i<=n;i++)scanf("%s",ss[i]+1); scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2); X1++;Y1++;X2++;Y2++; memset(d,63,sizeof(d));d[X1][Y1]=0; queue<node>Q;Q.push({X1,Y1}); while(Q.size()) { int x=Q.front().x,y=Q.front().y;Q.pop(); for(int i=0;i<=3;i++) { int tx=x+dx[i],ty=y+dy[i]; if(tx<=n && tx>=1 && ty<=m && ty>=1) { if(ss[x][y]!=ss[tx][ty]) { if(d[x][y]+1<d[tx][ty]) { d[tx][ty]=d[x][y]+1; Q.push({tx,ty}); } } else { if(d[x][y]<d[tx][ty]) { d[tx][ty]=d[x][y]; Q.push({tx,ty}); } } } } } printf("%d\n",d[X2][Y2]); } return 0; }
- 1
信息
- ID
- 760
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 60
- 已通过
- 18
- 上传者