1286: 海战

http://tjuacm.chaosheng.top/problem.php?id=1286
https://www.luogu.com.cn/problem/P1135

我自己写的，每次扫描到‘#’就bfs找和他相连的所有‘#’，找到所有的之后判断是否是矩形，是则船数加1，否则输出bad，跳出循环。
判断：如果是矩形，则有(r - l+ 1) * (e - b + 1) == k，k是相连的‘#’数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
const int N = 1010; 

int R, C;
char matrix[N][N];
bool visit[N][N];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0}; 

struct pos{
    int x;
    int y;
};

bool bfs(int x, int y){
    memset(visit, false, sizeof(visit));
    queue<pos> q;
    pos f, v;
    f.x = x;
    f.y = y;
    matrix[f.x][f.y] = '.';
    q.push(f);
    int l = x, r = x;
    int b = y, e = y;
    int k = 1;


    while(!q.empty()){
        f = q.front();
        q.pop();

        //printf("k = %d f    x = %d fy = %d\n", k, f.x, f.y);
        for(int i = 0; i < 4; i++){
            v.x = f.x + dx[i];
            v.y = f.y + dy[i];
            //printf("k = %d   v  x = %d vy = %d\n", k, v.x, v.y);
            if(v.x >= 0 && v.x < R && v.y >= 0 && v.y < C && matrix[v.x][v.y] == '#') {
                matrix[v.x][v.y] = '.';
                l = min(l, v.x);
                r = max(r, v.x);
                b = min(b, v.y);
                e = max(e, v.y);
                k++;
                q.push(v);
                //printf("k = %d l = %d r = %d b = %d e = %d\n", k, l ,r, b, e);
            }
        }            
    }
    //printf("s = %d\n", k);
    if((r - l+ 1) * (e - b + 1) == k) return true;
    else return false;
}

int main(){
    cin >> R >> C;

    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> matrix[i][j];
        }
    }

    int cnt = 0;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            if(matrix[i][j] == '#'){
                if(bfs(i, j)){
                    cnt++;
                }else{
                    printf("Bad placement.\n");
                    return 0;
                }
            }
        }
    }
    printf("There are %d ships.\n", cnt);
    return 0;
}