我的思路: 遍历第一行 每次遍历高度最高的,然后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;
}