88分BFS, 错#6 #11 求调
查看原帖
88分BFS, 错#6 #11 求调
415961
Luo_gu_ykc楼主2022/10/13 13:55
#include<bits/stdc++.h>

using namespace std;

const int N = 305;

int t;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
bool vis[N][N] = {0};

struct node{
	int x, y, step;
	bool f;
};

struct tp{
	int x, y;
};

void solve(){
	queue <node> q;
	vector <tp> s[35];
	int n, m, __x, __y;
	char c[N][N];
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> c[i][j];
			if(c[i][j] == '@'){
				__x = i;
				__y = j;
			} else if(c[i][j] >= 'A' && c[i][j] <= 'Z'){
				s[c[i][j] - 65].push_back({i, j});
			}
		}
	} 
	q.push({__x, __y, 0});
	while(!q.empty()){
		node v = q.front();
		q.pop();
		if(c[v.x][v.y] == '='){
			cout << v.step << "\n";
			return ;
		} 
		if(c[v.x][v.y] >= 'A' && c[v.x][v.y] <= 'Z' && v.f != 1){
			bool vf = 0;
			for(int i = 0; i < s[c[v.x][v.y] - 65].size(); i++){
				if(s[c[v.x][v.y] - 65][i].x == v.x && s[c[v.x][v.y] - 65][i].y == v.y){
					continue; 
				}
				q.push({s[c[v.x][v.y] - 65][i].x, s[c[v.x][v.y] - 65][i].y, v.step, 1});
				vf = 1;
			}
			if(vf){
				continue;
			}
		}
		for(int i = 0; i <= 3; i++){
			int fx = v.x + dx[i], fy = v.y + dy[i];
			if(fx >= 1 && fx <= n && fy >= 1 && fy <= m && !vis[fx][fy] && c[fx][fy] != '#'){
				vis[fx][fy] = 1;
				q.push({fx, fy, v.step + 1, 0});
			}
		}
	} 
	puts("-1");
	return ;
}

int main(){
	solve();
  	return 0;
}

2022/10/13 13:55
加载中...