#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define x first
#define y second
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int ans[1201][1201];
bool vit[1201][1201], arr[1201][1201];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str; cin >> str;
for (int j = 0; j < 3 * m; j++)
{
arr[i][j] = str[j % m] == 'B';
arr[i+n][j] = str[j % m] == 'B';
arr[i+2*n][j] = str[j % m] == 'B';
}
}
n *= 3; m *= 3;
for (int i = 0; i < n; i++)
{
if (vit[i][0]) continue;
queue<pi> q;
q.push({ i, 0 }); vit[i][0] = true;
bool inf = false;
vector<pi> vec;
while (q.size())
{
pi top = q.front(); q.pop();
vec.push_back(top);
if (top.y == m - 1 && top.x == i)
inf = true;
for (int j = 0; j < 4; j++)
{
int nx = top.x + dx[j], ny = top.y + dy[j];
if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
vit[nx][ny] || arr[top.x][top.y] != arr[nx][ny]) continue;
vit[nx][ny] = true;
q.push({nx, ny});
}
}
if (inf)
for (auto& p : vec)
ans[p.x][p.y] = -1;
}
memset(vit, false, sizeof(vit));
for (int i = 0; i < m; i++)
{
if (vit[0][i]) continue;
queue<pi> q;
q.push({ 0, i }); vit[0][i] = true;
bool inf = false;
vector<pi> vec;
while (q.size())
{
pi top = q.front(); q.pop();
vec.push_back(top);
if (top.x == n - 1 && top.y == i)
inf = true;
for (int j = 0; j < 4; j++)
{
int nx = top.x + dx[j], ny = top.y + dy[j];
if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
vit[nx][ny] || arr[top.x][top.y] != arr[nx][ny]) continue;
vit[nx][ny] = true;
q.push({ nx, ny });
}
}
if (inf)
for (auto& p : vec)
ans[p.x][p.y] = -1;
}
memset(vit, false, sizeof(vit));
for (int i = n/3; i < 2*n/3; i++)
{
for (int j = m/3; j < 2*m/3; j++)
{
if (ans[i][j] == -1 || vit[i][j]) continue;
queue<pi> q;
q.push({ i, j }); vit[i][j] = true;
vector<pi> vec;
while (q.size())
{
pi top = q.front(); q.pop();
vec.push_back(top);
for (int k = 0; k < 4; k++)
{
int nx = top.x + dx[k], ny = top.y + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m ||
vit[nx][ny] || arr[top.x][top.y] != arr[nx][ny]) continue;
vit[nx][ny] = true;
q.push({ nx, ny });
}
}
int sz = vec.size();
for (auto& p : vec)
ans[p.x][p.y] = sz;
}
}
for (int i = n/3; i < 2*n/3; i++)
{
for (int j = m/3; j < 2*m/3; j++)
cout << ans[i][j] << " ";
cout << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
90 ms |
12004 KB |
Output is partially correct |
| 2 |
Incorrect |
83 ms |
11408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
