#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int r, c;
vector<string> data;
vector<vector<int>> getCnt(vector<string> &field) {
int r = field.size(), c = field[0].size();
vector<vector<int>> ret(r, vector<int>(c, -1));
for(int i= 0; i < r; i++)
for(int j= 0; j< c;j++) {
if(ret[i][j] != -1) continue;
ret[i][j] = 0;
queue<tuple<int, int>> q;
q.push(make_tuple(i, j));
int cnt = 0;
vector<tuple<int, int>> coords;
while(!q.empty()) {
cnt++;
int y, x;
tie(y, x) = q.front();
coords.emplace_back(y, x);
q.pop();
const int mov[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for(int k = 0; k < 4; k++) {
int ny = y + mov[k][0];
int nx = x + mov[k][1];
if(ny >= 0 and ny < r and nx >= 0 and nx < c and ret[ny][nx] == -1 and field[ny][nx] == field[y][x]) {
ret[ny][nx] = 0;
q.push(make_tuple(ny, nx));
}
}
}
for(auto coord: coords) {
int y, x;
tie(y, x) = coord;
ret[y][x] = cnt;
}
}
return ret;
}
int main(void) {
cin >> r >> c;
data = vector<string>(r);
for(int i =0 ; i <r; i++) cin >> data[i];
vector<string> smallf(r * 3);
vector<string> largef(r * 5);
for(int i = 0; i < 3 * r; i++)
for(int j = 0; j < 3; j++)
smallf[i] += data[i % r];
for(int i =0 ; i < 5 * r; i++)
for(int j = 0; j < 5; j++)
largef[i] += data[i % r];
auto scnt = getCnt(smallf);
auto lcnt = getCnt(largef);
for(int i =0; i < r; i++) {
for(int j = 0; j < c; j++)
if(scnt[i + r][j + c] == lcnt[i + r * 2][j + c * 2])
cout << scnt[i + r][j + c] << " ";
else cout << "-1 ";
cout << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
276 ms |
36060 KB |
Output is correct |
| 2 |
Incorrect |
286 ms |
40160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
