【题解】洛谷P1331 海战

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

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

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

3.否则输出连通块个数

代码:

#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;
}