求帮助
查看原帖
求帮助
1072433
oneday001楼主2023/10/30 20:57

我的思路: 遍历第一行 每次遍历高度最高的,然后bfs这个点 为什么我写不出来

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<vector<int>>city(501, vector<int>(501, 0));
vector<vector<bool>>vis(501, vector<bool>(501,false));
int sum;
int main() {
	int next[4][2] = { 0,1,1,0,-1,0,0,-1 };
	int n, m;//n行m列
	int Max=INT_MIN, maxj=0;//Max为第一行未被访问的最大的海拔高度 maxj是它的列下标
	cin >> n >> m;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> city[i][j];//城市的海拔高度
			}
		}
	
	bool flag = false;//是否所有城市都有水利装置
	int count = 0;//水利装置的数量
	while (1) {
		for (int j = 0; j < m; j++) {
			if (vis[0][j] == false) {
				if (Max < city[0][j]) {//找最高海拔的城市
					Max = city[0][j];
					maxj = j;
				}
			}
		}
		Max = INT_MIN;
		vis[0][maxj] = true;
		sum++;//第一行被遍历城市的数量
		if (sum > m)break;//如果第一行被遍历完了就break
		queue<pair<int,int>>que;
		que.push({0,maxj});
		while (!que.empty()) {//bfs
			pair<int,int> cur = que.front(); que.pop();
			for (int k = 0; k <= 3; k++) {
				int nexti = cur.first + next[k][0];
				int nextj = cur.second + next[k][1];
				if (nexti < 0 || nexti >= n || nextj < 0 || nextj >= m)continue;
				if (city[cur.first][cur.second] > city[nexti][nextj]&&vis[nexti][nextj]==false) {
					vis[nexti][nextj] = true;
					count++;
					que.push({ nexti,nextj });
					if (count == (n - 1) * m) {
						flag = true;
						break;
					}
				}
			}
		}
		if (flag) {
			break;
		}
	}
	if (flag) {
		cout << 1 << endl << sum;
	}
	else {
		cout << 0 <<endl<< (n - 1) * m - count;
	}
	return 0;
}
2023/10/30 20:57
加载中...