1 solutions

  • 0
    @ 2025-10-28 14:00:48
    #include<bits/stdc++.h>
    using namespace std;
    int d[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    struct P { int x, y; };
    bool g[1000][1000];
    bool v[1000][1000];
    int r, c;
    bool check(const vector<P>& cmp) {
        int minx = r, maxx = -1;
        int miny = c, maxy = -1;
        for (const auto& p : cmp) {
            minx = min(minx, p.x);
            maxx = max(maxx, p.x);
            miny = min(miny, p.y);
            maxy = max(maxy, p.y);
        }
        int area = (maxx - minx + 1) * (maxy - miny + 1);
        if (cmp.size() != area) return false;
        for (int i = minx - 1; i <= maxx + 1; ++i) {
            for (int j = miny - 1; j <= maxy + 1; ++j) {
                if (i >= minx && i <= maxx && j >= miny && j <= maxy) continue;
                if (i >= 0 && i < r && j >= 0 && j < c && g[i][j]) return false;
            }
        }
        return true;
    }
    void bfs(int x, int y, vector<P>& cmp) {
        queue<P> q;
        q.push({x, y});
        v[x][y] = true;
        cmp.push_back({x, y});
        
        while (!q.empty()) {
            P cur = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = cur.x + d[i][0];
                int ny = cur.y + d[i][1];
                if (nx >= 0 && nx < r && ny >= 0 && ny < c && !v[nx][ny] && g[nx][ny]) {
                    v[nx][ny] = true;
                    q.push({nx, ny});
                    cmp.push_back({nx, ny});
                }
            }
        }
    }
    int main() {
        cin >> r >> c;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                char ch; cin >> ch;
                g[i][j] = (ch == '#');
            }
        }
        memset(v, 0, sizeof(v));
        int cnt = 0;
        bool ok = true;
        for (int i = 0; i < r && ok; ++i) {
            for (int j = 0; j < c && ok; ++j) {
                if (g[i][j] && !v[i][j]) {
                    vector<P> cmp;
                    bfs(i, j, cmp);
                    if (!check(cmp)) ok = false;
                    else cnt++;
                }
            }
        }
        if (ok) cout << "There are " << cnt << " ships." << endl;
        else cout << "Bad placement." << endl;
        return 0;
    }
    
    • 1

    Information

    ID
    328
    Time
    800ms
    Memory
    128MiB
    Difficulty
    2
    Tags
    # Submissions
    3
    Accepted
    3
    Uploaded By