#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
char in[405];
bool fl[400][400], v1[400*400], v2[400*400];
int dx[4] = { -1,0,0,1 }, dy[4] = { 0,1,-1,0 }, n, m;
vector<int> g[400 * 400], cc;
int ans[400*400], v[400][400], nf, len[400*400];
inline int pti(int y, int x)
{
return y*m + x;
}
void foo(int i, int j)
{
if (v[i][j] != 0) return;
nf++;
v[i][j] = nf;
queue<int> q;
q.emplace(pti(i, j));
while (!q.empty())
{
int idx = q.front();
int y = idx / m;
int x = idx % m;
q.pop();
ans[nf]++;
for (int e : g[idx])
{
int yy = e / m, xx = e%m;
if (v[yy][xx]) continue;
v[yy][xx] = nf;
q.emplace(e);
}
}
return;
}
bool bar(int c, int p)
{
v1[c] = v2[c] = true;
cc.push_back(c);
bool cycle = false;
for (int e : g[c])
{
if (e == p) continue;
if (v1[e])
{
int l = len[c] + 1 - len[e];
if (l & 1) cycle = true;
}
else
{
len[e] = len[c] + 1;
cycle |= bar(e, c);
}
}
if (cycle) ans[c] = -1;
v1[c] = false;
return cycle;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)
{
scanf("%s", in);
for (int j = 0; j < m; j++)
fl[i][j] = in[j] == 'B';
}
for(int i=0;i<n;i++)
for (int j = 0; j < m; j++)
{
int p1 = pti(i, j);
for (int d = 0; d < 4; d++)
{
int x = j + dx[d], y = i + dy[d];
if (x < 0 || x >= m || y < 0 || y >= n) continue;
if (fl[i][j] != fl[y][x]) continue;
int p2 = pti(y, x);
g[p1].push_back(p2);
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
foo(i, j);
for (int i = 0; i <= nf; i++) g[i].clear();
for (int i = 0; i < n; i++)
{
if (fl[i][0] != fl[i][m - 1]) continue;
g[v[i][0]].push_back(v[i][m - 1]);
g[v[i][m - 1]].push_back(v[i][0]);
}
for (int i = 0; i < m; i++)
{
if (fl[0][i] != fl[n - 1][i]) continue;
g[v[0][i]].push_back(v[n - 1][i]);
g[v[n - 1][i]].push_back(v[0][i]);
}
for (int i = 0; i <= nf; i++)
{
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
for (int i = 1; i <= nf; i++)
{
if (v2[i]) continue;
v2[i] = true;
len[i] = 0;
cc.clear();
bar(i,0);
int sum = 0;
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (int i : cc) sum += ans[i];
if (sum < 0) sum = -1;
for (int i : cc) ans[i] = sum;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
printf("%d ", ans[v[i][j]]);
}
puts("");
}
}
Compilation message
YZ.cpp: In function 'void foo(int, int)':
YZ.cpp:29:7: warning: unused variable 'y' [-Wunused-variable]
int y = idx / m;
^
YZ.cpp:30:7: warning: unused variable 'x' [-Wunused-variable]
int x = idx % m;
^
YZ.cpp: In function 'int main()':
YZ.cpp:70:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
YZ.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", in);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
59 ms |
13048 KB |
Output is partially correct |
| 2 |
Correct |
63 ms |
13048 KB |
Output is correct |
| 3 |
Partially correct |
53 ms |
13048 KB |
Output is partially correct |
| 4 |
Correct |
59 ms |
13048 KB |
Output is correct |
| 5 |
Correct |
63 ms |
13048 KB |
Output is correct |
| 6 |
Correct |
66 ms |
13048 KB |
Output is correct |
| 7 |
Correct |
53 ms |
13048 KB |
Output is correct |
| 8 |
Partially correct |
53 ms |
13048 KB |
Output is partially correct |
| 9 |
Correct |
59 ms |
13048 KB |
Output is correct |
| 10 |
Correct |
49 ms |
13048 KB |
Output is correct |
| 11 |
Correct |
56 ms |
13048 KB |
Output is correct |
| 12 |
Correct |
93 ms |
13048 KB |
Output is correct |
| 13 |
Partially correct |
59 ms |
13048 KB |
Output is partially correct |
| 14 |
Partially correct |
53 ms |
13048 KB |
Output is partially correct |
| 15 |
Correct |
69 ms |
13048 KB |
Output is correct |
| 16 |
Partially correct |
53 ms |
13048 KB |
Output is partially correct |
| 17 |
Partially correct |
39 ms |
13048 KB |
Output is partially correct |
| 18 |
Correct |
43 ms |
13048 KB |
Output is correct |
| 19 |
Correct |
56 ms |
12784 KB |
Output is correct |
| 20 |
Partially correct |
53 ms |
12652 KB |
Output is partially correct |
| 21 |
Correct |
59 ms |
11332 KB |
Output is correct |
| 22 |
Correct |
46 ms |
12916 KB |
Output is correct |
| 23 |
Partially correct |
73 ms |
12784 KB |
Output is partially correct |
| 24 |
Partially correct |
59 ms |
12916 KB |
Output is partially correct |
| 25 |
Correct |
59 ms |
13048 KB |
Output is correct |
| 26 |
Correct |
0 ms |
8032 KB |
Output is correct |
| 27 |
Correct |
0 ms |
8032 KB |
Output is correct |
| 28 |
Correct |
0 ms |
8164 KB |
Output is correct |
| 29 |
Correct |
0 ms |
8164 KB |
Output is correct |
| 30 |
Correct |
3 ms |
8032 KB |
Output is correct |
| 31 |
Correct |
0 ms |
8032 KB |
Output is correct |
| 32 |
Partially correct |
0 ms |
8032 KB |
Output is partially correct |
| 33 |
Partially correct |
3 ms |
8032 KB |
Output is partially correct |
| 34 |
Correct |
0 ms |
8032 KB |
Output is correct |
| 35 |
Correct |
0 ms |
8032 KB |
Output is correct |
| 36 |
Correct |
3 ms |
8428 KB |
Output is correct |
| 37 |
Correct |
6 ms |
8296 KB |
Output is correct |
| 38 |
Correct |
6 ms |
8296 KB |
Output is correct |
| 39 |
Partially correct |
6 ms |
8296 KB |
Output is partially correct |
| 40 |
Correct |
6 ms |
8428 KB |
Output is correct |
