19pts求调
查看原帖
19pts求调
947029
Chen_Three楼主2024/11/28 19:48
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
	int startx, starty, endx, endy;
}chuansong[100]; 
char a[305][305];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool used[305][305];
int n, m, t;
int zhongdianx, zhongdiany, qidianx, qidiany;
bool is_alive(int x, int y){
	return x >= 1 && x <= n && y >= 1 && y <= m && !used[x][y];
}
void bfs(){
	queue<pair<pair<int, int>, int> > q;
	q.push(make_pair(make_pair(qidianx, qidiany), 0));
	used[qidianx][qidiany] = 1;
	while(!q.empty()){
		auto now = q.front();
		q.pop();
		for(int i = 0; i < 4; i++){
			int tx = now.first.first + dx[i], ty = now.first.second + dy[i];
			if(is_alive(tx, ty)){
				if(tx == zhongdianx && ty == zhongdiany){
					cout << now.second + 1;
					return;
				}
				for(int j = 1; j <= t; j++){
					if(chuansong[j].startx == tx && chuansong[j].startx == ty){
						tx = chuansong[j].endx;
						ty = chuansong[j].endy;
					}
				}
				if(is_alive(tx, ty)){
					used[tx][ty] = 1;
					q.push(make_pair(make_pair(tx, ty), now.second + 1));
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		string s;
		cin >> s;
		for(int j = 1; j <= m; j++){
			a[i][j] = s[j - 1];
			if(a[i][j] == '#') used[i][j] = 1;
			if(a[i][j] == '=') zhongdianx = i, zhongdiany = j;
			if(a[i][j] == '@') qidianx = i, qidiany = j;
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] >= 'A' && a[i][j] <= 'Z'){
				bool flag = 0;
				for(int k = 1; k <= n; k++){
					for(int l = 1; l <= m; l++){
						if(a[k][l] == a[i][j] && !(i == k && j == l)){
							flag = 1;
							chuansong[++t] = (node){i, j, k, l};
							break;
						}
					}
					if(flag) break;
				}
			}
		}
	}
	//for(int i = 1; i <= t; i++) cout << chuansong[i].startx << ' ' << chuansong[i].starty << ' ' << chuansong[i].endx <<' ' <<chuansong[i].endy << '\n';
	bfs();
 	return 0;
}
2024/11/28 19:48
加载中...