wsm我的BFS根本就没有在循环内入队
查看原帖
wsm我的BFS根本就没有在循环内入队
777131
IDNo1楼主2023/4/20 21:40
#include<bits/stdc++.h>
using namespace std;
int n, m;
char s[301][301];
int sx, sy, ex, ey, step;
vector<pair<int, int> > b[27];
short int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
void set_check(){
	for (int i = 1;i <= 26;i ++){
		if (b[i].size()){
			cout << char(i - 1 + 'A') << ":";
			for (int l = 0;l < b[i].size();l ++){
				cout << b[i][l].first << " " << b[i][l].second << "        ";	
			}
			puts("");
		}
	}
}
int main()
{
    //ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i ++){
		for (int j = 1;j <= m;j ++){
			cin >> s[i][j];
			if (s[i][j] == '@'){
				sx = i, sy = j;
			}
			else if (s[i][j] >= 'A' && s[i][j] <= 'Z'){
				b[s[i][j] - 'A' + 1].push_back({i, j});
			}
			else if (s[i][j] == '='){
				ex = i, ey = j;
			}
		}
	}
	//set_check();
	queue<pair<int, int> > q;
	q.push({sx, sy});
	while (!q.empty()){
		++ step;
		pair<int, int> x = q.front();
		//cout << x.first << " "<<x.second<<"\n";
		q.pop();
		if (x.first == ex && x.second == ey){
			//cout << "have got.\n";
			break;
		}
		for (int i = 1;i <= 4;i ++){
			//cout<<1;
			char u = s[x.first + dx[i]][x.first + dy[i]];
			if (u == '.' || (u >= 'A' && u <= 'Z'))q.push({x.first + dx[i], x.second + dy[i]});
		}
		char v = s[x.first][x.second];
		if (v >= 'A' && v <= 'Z'){
			//cout<<1;
			if (b[v][0].first == x.first && b[v][0].second == x.second)q.push({b[v][1].first, b[v][1].second});
			else q.push({b[v][0].first, b[v][0].second});
		}
	}
	cout << step;
    return 0;
}
2023/4/20 21:40
加载中...