求调
查看原帖
求调
1280338
cyx12楼主2024/7/24 09:37
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <vector>
using namespace std;
const int N=505,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
struct node{int x,y;};
char a[N][N];
bool vis[N][N];
int d[N][N];
int n,m,x1,y1,x2,y2;
void bfs(){
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[x1][y1]=0;
    deque<node> q; 
    q.push_back((node){x1,y1});
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;q.pop_front();
        if(vis[x][y]) continue;
        vis[x][y]=1;
        for(int i=0;i<4;i++){ 
            int nx=x+dx[i],ny=y+dy[i],w;
            if(nx>n||nx<1||ny>m||ny<1) continue;
            if(a[nx][ny]==a[x][y]) w=0;
            else w=1;
            if(d[x][y]+w<d[nx][ny]){
                d[nx][ny]=d[x][y]+w;
                if(w==0) q.push_front(node{nx,ny});
                else q.push_back(node{nx,ny}); 
            } 
        }
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)&&n&&m){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1++,y1++,x2++,y2++;
        bfs();
        printf("%d\n",d[x2][y2]);
    }
    return 0;
}
2024/7/24 09:37
加载中...