QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #90118 | #3350. Counting Sheep | ChatGPT | AC ✓ | 13ms | 3356kb | C++ | 1.6kb | 2023-03-22 13:27:25 | 2023-03-22 13:27:42 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
void bfs(vector<string>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = true;
while (!q.empty()) {
int cur_x = q.front().first;
int cur_y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int new_x = cur_x + dx[i];
int new_y = cur_y + dy[i];
if (new_x >= 0 && new_x < grid.size() && new_y >= 0 && new_y < grid[0].size()) {
if (grid[new_x][new_y] == '#' && !visited[new_x][new_y]) {
visited[new_x][new_y] = true;
q.push({new_x, new_y});
}
}
}
}
}
int count_flocks(vector<string>& grid) {
int h = grid.size();
int w = grid[0].size();
vector<vector<bool>> visited(h, vector<bool>(w, false));
int count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (grid[i][j] == '#' && !visited[i][j]) {
bfs(grid, visited, i, j);
count++;
}
}
}
return count;
}
int main() {
int t;
cin >> t;
while (t--) {
int h, w;
cin >> h >> w;
vector<string> grid(h);
for (int i = 0; i < h; i++) {
cin >> grid[i];
}
int count = count_flocks(grid);
cout << count << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 3356kb
input:
100 1 1 . 1 1 # 1 100 #################################################################################################### 1 100 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. 1 100 .#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#######.#.#.#.#.#.#.#.#...
output:
0 1 1 50 44 0 1 2 1 1 0 4 5000 25 4 65 46 36 268 218 108 31 274 77 82 294 147 58 13 294 138 135 115 358 158 25 103 509 383 307 40 361 51 81 24 26 219 8 266 157 27 506 176 44 83 222 30 165 224 18 44 441 381 101 58 167 237 175 125 310 185 74 102 20 248 413 246 325 238 136 236 18 410 327 42 18 272 55 1...
result:
ok 100 lines