温州市城乡建设厅网站首页,商场网站建设模板,吉林省水土保持生态建设网站,百度文章收录提交入口解题思路: bfs:遍历所有未遍历过的陆地#xff0c;通过bfs计算出当前位置连通陆地的数量cnt#xff0c;以及被淹没陆地的数量bound,若cnt bound表示完整淹没的一个岛屿
dfs:将连通块全部标记#xff0c;如果这个连通块全部都会淹没#xff0c;则答案1#xff0c;如果这个… 解题思路: bfs:遍历所有未遍历过的陆地通过bfs计算出当前位置连通陆地的数量cnt以及被淹没陆地的数量bound,若cnt bound表示完整淹没的一个岛屿
dfs:将连通块全部标记如果这个连通块全部都会淹没则答案1如果这个连通块里面有无法被淹没的就不1
bfs代码如下
#include iostream
#include queue
#include cstring
using namespace std;
typedef pairint, intPII;
#define x first
#define y second
const int N 1010;
char g[N][N];
int res 0;
bool st[N][N];
int n;int dx[] {0, 0, 1, -1}, dy[] {1, -1, 0, 0};void bfs(int x, int y, int cnt, int bound) {queuePIIq;q.push({x, y});st[x][y] true;while (q.size()) {bool is_bound false;PII t q.front();cnt;q.pop();for (int i 0; i 4; i) {int xx t.x dx[i], yy t.y dy[i];if (xx 0 || xx n || yy 0 || yy n)continue;if (g[xx][yy] .) {is_bound true;continue;}if (st[xx][yy])continue;st[xx][yy] true;q.push({xx, yy});}if (is_bound) {bound;}}}int main() {cin n;for (int i 0; i n; i)cin g[i];for (int i 0; i n; i)for (int j 0; j n; j) {if (g[i][j] # !st[i][j]) {int bound 0, cnt 0;bfs(i, j, cnt, bound);if (cnt bound)res;}}cout res endl;return 0;
}
dfs代码如下:
#include iostream
using namespace std;
const int N 1010;
char g[N][N];
int ans;bool flag;int dx[] {0, 0, 1, -1}, dy[] {1, -1, 0, 0};
bool vis[N][N];void dfs(int x, int y) {if (g[x 1][y] # g[x - 1][y] # g[x][y 1] # g[x][y - 1] #)flag true;///上下左右都是陆地不会淹没for (int i 0; i 4; i) {int xx x dx[i], yy y dy[i];if (g[xx][yy] # !vis[xx][yy]) {vis[xx][yy] true;dfs(xx, yy);}}
}int main() {int n;cin n;for (int i 1; i n; i)cin g[i];for (int i 1; i n; i)for (int j 1; j n; j) {if (g[i][j] # !vis[i][j]) {flag false;dfs(i, j);if (!flag)ans;}}cout ans endl;return 0;
}
