luoguP1331 海战

与其他题解不同的矩形判断方式:

1.在 dfs 出所有连通块时假定每个连通块都是矩形,保存其 xx , yy 的最大值。

2.遍历所有连通块(矩形),如果矩形的外圈有"#"或者内部有空位说明当前连通块不合法,直接退出。

3.否则输出连通块个数

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
using namespace std;
struct BoxData {//假设为矩形的连通块
int x1, y1, x2, y2;
};
int r, c;
bool arr[1010][1010], vis[1010][1010];
vector<BoxData> boxes;
void dfs(int x, int y, BoxData &data) {//找连通块并计算矩形左上,右下点坐标
if(x < 1 || x > r || y < 1 || y > c || !arr[x][y] || vis[x][y]) return;
vis[x][y] = true;
data.x2 = max(data.x2, x + 1), data.y2 = max(data.y2, y + 1);//最终结果包括外圈的空位
dfs(x + 1, y, data);
dfs(x - 1, y, data);
dfs(x, y + 1, data);
dfs(x, y - 1, data);
}
bool checkBox(BoxData data) {//检查当前矩形是否合法
for(int i = data.x1; i <= data.x2; i++) if(arr[i][data.y1]) return false;
for(int i = data.x1; i <= data.x2; i++) if(arr[i][data.y2]) return false;
for(int i = data.y1; i <= data.y2; i++) if(arr[data.x1][i]) return false;
for(int i = data.y1; i <= data.y2; i++) if(arr[data.x2][i]) return false;
for(int i = data.x1 + 1; i <= data.x2 - 1; i++)
for(int j = data.y1 + 1; j <= data.y2 - 1; j++)
if(!arr[i][j]) return false;
return true;
int main() {
cin >> r >> c;
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++) {
char ch;
cin >> ch;
arr[i][j] = ch == '#' ? 1 : 0;
}
//普通的求连通块
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++) {
if(!arr[i][j] || vis[i][j]) continue;
BoxData cur = {i - 1, j - 1, 0, 0};
dfs(i, j, cur);
boxes.push_back(cur);
}
bool flag = true;
for(auto box : boxes) {//遍历
//cout << box.x1 + 1 << ' ' << box.y1 + 1 << ' ' << box.x2 - 1 << ' ' << box.y2 - 1 << endl;
if(!checkBox(box)) {
flag = false;
break;
}
}
if(flag) cout << "There are " << boxes.size() << " ships." << endl;
else cout << "Bad placement." << endl;
system("pause");
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!