60分WA2个点,求调
查看原帖
60分WA2个点,求调
783810
furina_yyds楼主2024/9/7 17:53
#include<bits/stdc++.h>
using namespace std;
int n, m;
char s[1005][1005];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0}; 
int dis[1005][1005];
struct point{
	int x, y, c;
};
void bfs(int sx, int sy){
	deque<point>q;
	point now;
	now.x = sx, now.y = sy, now.c = 0;
	q.push_front(now);
	dis[sx][sy] = 0; 
	while(!q.empty()){
		int x = q.front().x, y = q.front().y, c = q.front().c;
		q.pop_front();
		if(x == n - 1 && y == m - 1) break;
		for(int i = 0; i < 4; i++){
			int zx = x + dx[i], zy = y + dy[i];
			if(zx < 0 || zx >= n || zy < 0 || zy >= m) continue;
			if(s[x][y] == s[zx][zy] && c < dis[zx][zy]){
				dis[zx][zy] = c;
				point now;
				now.x = zx, now.y = zy, now.c = c;
				q.push_front(now);
			}
			else if(s[zx][zy] != s[x][y] && c + 1 < dis[zx][zy]){
				dis[zx][zy] = c + 1;
				point now;
				now.x = zx, now.y = zy, now.c = c + 1;
				q.push_back(now);
			}
		}
	}
}
int main(){
	while(1){
		memset(dis, 0x3f, sizeof(dis));
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0)break;
		for(int i = 0;i < n;i++)
			cin >> s[i];
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		bfs(x1, y1);
		printf("%d\n", dis[x2][y2]);
	}	
	return 0;
}
2024/9/7 17:53
加载中...