我又来求救了
查看原帖
我又来求救了
1503208
convie楼主2025/1/16 22:02

第二个测试点死活过不去,来个大佬救救呀。

#include<iostream>
#include<cstring>
#include <queue>
using namespace std;
#define MAXN 1010
#define x first
#define y second
typedef pair<int,int> PII;
char e[MAXN][MAXN];
deque<PII> q;
int n,m;
bool st[MAXN][MAXN];
int tx[]={0,0,1,-1};
int ty[]={1,-1,0,0};
int dis[MAXN][MAXN];
int bfs(int x1,int y1,int x2,int y2){
	memset(st, 0 ,sizeof st);
	memset(dis,0,sizeof dis);
	q.push_back({x1,y1});
	//dis[x1][y1]
	while(!q.empty()){
		PII t=q.front();
		q.pop_front();
		if(t.x==x2&&t.y==y2) return dis[t.x][t.y];
		for(int i=0;i<4;i++){
			int nx=t.x+tx[i];
			int ny=t.y+ty[i];
			if(nx<1||nx>n||ny<1||ny>m)continue;
			if(st[nx][ny])continue;
			if(e[nx][ny]==e[t.x][t.y]){
				q.push_front({nx,ny});
				dis[nx][ny]=dis[t.x][t.y];
				st[nx][ny]=true;
			}else {
				q.push_back({nx,ny});
				dis[nx][ny]=dis[t.x][t.y]+1;
				st[nx][ny]=true;
			}
		}
	}
	return -1;
}
int main(){
	while(cin>>n>>m&&n&&m){
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		scanf(" %c",&e[i][j]);
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		cout<<bfs(x1+1,y1+1,x2+1,y2+1)<<endl;
	}
	return 0;
}

救命呀

2025/1/16 22:02
加载中...