1 solutions
-
0
#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