题目描述
blablabla
讲究一个要发现岛只能四个方向走,海可以八个方向走,岛只要四个方向走不了就连不起来了。
海的话要八个方向走不了才连不起来。
解
#include <cstdint>
#include <iostream>
#include <queue>
#include <string>
#include <type_traits>
using namespace std;
typedef pair<int, int> PII;
const int N = 100;
int g[N][N];
int n, m;
bool stSea[N][N]; // 标记走过的海和岛
bool stRoad[N][N];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
//海可以的走向
int ddx[4] = {-1, 0, 0, 1};
int ddy[4] = {0, -1, 1, 0};
//岛可以的走向
int ans = 0;
//答案,记录有多少个岛
bool check(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m); } //检查是否越界
void bfsRoad(int x, int y) {
queue<PII> q; //队列用于记录,原理就是先把最开始的入口读进来,每次循环最开始取出一个坐标,然后如果这个它个坐标四周都走不了,那循环就停止,如果有可以走的地方,继续把可以走的坐标存进来
stRoad[x][y] = true; //初始进入的岛标记为走过
q.push({x, y}); //把当前岛的坐标记录
while (q.size()) { //只要队列里记录还有可以走的地方就循环
auto t = q.front(); //取出一个可以走的坐标
q.pop(); //清除队列里使用过的坐标
for (int i = 0; i < 4; i++) { //检查四个方位,所以循环四次
int nx = t.first + ddx[i]; //把当前坐标加上可以走的方向,就是准备用于查看是否能走到的坐标
int ny = t.second + ddy[i];
if (check(nx, ny) && g[nx][ny] && !stRoad[nx][ny]) { //检查,如果刚刚得到的坐标是合法的,同时是岛屿可以走,同时它没有被标记走过
stRoad[nx][ny] = true; // 就把这个坐标标记成走过
q.push({nx, ny}); // 且把他记录到队列
}
}
}
}
void bfsSea(int x, int y) {
queue<PII> q;
stSea[x][y] = true;
q.push({x, y}); //和岛的部分完全一致
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = 0; i < 8; i++) { //海有八个走向所以循环八次
int nx = t.first + dx[i];
int ny = t.second + dy[i];
if (check(nx, ny) && !g[nx][ny] && !stSea[nx][ny]) {
stSea[nx][ny] = true;
q.push({nx, ny});
}
if (check(nx, ny) && g[nx][ny] && !stRoad[nx][ny]) { //这里判断有没有发现岛,发现岛了在搜索岛有多大
ans++; //发现了就先给答案+1
bfsRoad(nx, ny); //然后进入岛的搜索
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
cin >> n >> m;
ans = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
stSea[i][j] = stRoad[i][j] = false;
}
}//把岛和海的标记都初始化一下
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
g[i][j] = s[j] - '0';
}
}//读入图
bool flag = false;//先弄一个标记,因为子岛屿不算是岛屿,所以要检查是不是一个岛全给包起来了,包起来答案就是1
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!i || i == n - 1 || !j || j == m - 1) { // 我们是从最外围的海开始走,所以这里先判断是不是在四条边上
if (!g[i][j] && !stSea[i][j]) {//再判断这不是岛的同时也没有走过的海
flag = true; //那就不是四条边都是岛
bfsSea(i, j); //开搜
}
}
}
}
if (!flag) { //遇到特例,四条边全是岛
ans = 1; //答案只能为1
}
cout << ans << endl;
}
}