60pts求调,悬关
查看原帖
60pts求调,悬关
1419415
tommy24楼主2025/1/22 15:41
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
struct node{
	int x;
	int y;
	int cost;
}t;
deque <node> q;
bool map1[MAXN][MAXN], vis[MAXN][MAXN];

int main(){
	while(true){
		int n, m = 0;
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		int ans = 9999999;
		memset(vis, 0, sizeof(vis));
		for(int i = 1; i <= n; i ++){
			string x;
			cin >> x;
			for(int j = 1; j <= m; j ++){
				if(x[j - 1] == '#') map1[i][j] = 1;
				else map1[i][j] = 0;
			}
		}
		int x1, y1, x2, y2 = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		q.push_back({x1 + 1, y1 + 1, 0});
		vis[x1 + 1][y1 + 1] = 1;
		while(!q.empty()){
			t = q.front();
			q.pop_front();
			if(t.x == x2 + 1 && t.y == y2 + 1){
                //cout << t.cost << endl;
				ans = min(ans, t.cost);
				break;
			}
			for(int i = 0; i <= 3; i ++){
				int nx = t.x + dx[i];
				int ny = t.y + dy[i];
				if(nx > 0 && nx <= m && ny > 0 && ny <= n && !vis[nx][ny]){
					if(map1[nx][ny] == map1[t.x][t.y]){
						q.push_front({nx, ny, t.cost});
						vis[nx][ny] = 1;
					}else{
						q.push_back({nx, ny, t.cost + 1});
						vis[nx][ny] = 1;
					}
				}
			}
		}
		cout << ans << endl;
	}
} 
2025/1/22 15:41
加载中...