#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct edge
{
int t, w;
edge(int t, int w) : t(t), w(w) {}
bool operator <(const edge &o) const
{
return t < o.t;
}
bool operator == (const edge &o) const
{
return t == o.t;
}
};
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;
vector<edge> gg[400 * 400];
int ans[400 * 400], v[400][400], nf;
long long 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 (auto e : gg[c])
{
if (e.t == p) continue;
if (v1[e.t])
{
long long l = len[c] + e.w - len[e.t];
if (l) cycle = true;
}
else
{
len[e.t] = len[c] + e.w;
cycle |= bar(e.t, 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 < n; i++)
{
if (fl[i][0] != fl[i][m - 1]) continue;
gg[v[i][0]].push_back(edge(v[i][m - 1],1));
gg[v[i][m - 1]].push_back(edge(v[i][0],-1));
}
for (int i = 0; i < m; i++)
{
if (fl[0][i] != fl[n - 1][i]) continue;
gg[v[0][i]].push_back(edge(v[n - 1][i],100000));
gg[v[n - 1][i]].push_back(edge(v[0][i],-100000));
}
for (int i = 0; i <= nf; i++)
{
sort(gg[i].begin(), gg[i].end());
gg[i].erase(unique(gg[i].begin(), gg[i].end()), gg[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:46:7: warning: unused variable 'y' [-Wunused-variable]
int y = idx / m;
^
YZ.cpp:47:7: warning: unused variable 'x' [-Wunused-variable]
int x = idx % m;
^
YZ.cpp: In function 'int main()':
YZ.cpp:87: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:90: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 |
79 ms |
17424 KB |
Output is partially correct |
| 2 |
Correct |
56 ms |
17424 KB |
Output is correct |
| 3 |
Correct |
66 ms |
17424 KB |
Output is correct |
| 4 |
Correct |
63 ms |
17424 KB |
Output is correct |
| 5 |
Correct |
66 ms |
17424 KB |
Output is correct |
| 6 |
Correct |
59 ms |
17424 KB |
Output is correct |
| 7 |
Correct |
56 ms |
17424 KB |
Output is correct |
| 8 |
Correct |
53 ms |
17424 KB |
Output is correct |
| 9 |
Correct |
59 ms |
17424 KB |
Output is correct |
| 10 |
Correct |
53 ms |
17424 KB |
Output is correct |
| 11 |
Correct |
56 ms |
17424 KB |
Output is correct |
| 12 |
Correct |
53 ms |
17424 KB |
Output is correct |
| 13 |
Correct |
56 ms |
17424 KB |
Output is correct |
| 14 |
Correct |
59 ms |
17424 KB |
Output is correct |
| 15 |
Correct |
56 ms |
17424 KB |
Output is correct |
| 16 |
Partially correct |
39 ms |
17424 KB |
Output is partially correct |
| 17 |
Partially correct |
39 ms |
17424 KB |
Output is partially correct |
| 18 |
Correct |
49 ms |
17424 KB |
Output is correct |
| 19 |
Correct |
63 ms |
17160 KB |
Output is correct |
| 20 |
Partially correct |
73 ms |
17028 KB |
Output is partially correct |
| 21 |
Correct |
59 ms |
15708 KB |
Output is correct |
| 22 |
Correct |
56 ms |
17292 KB |
Output is correct |
| 23 |
Partially correct |
66 ms |
17160 KB |
Output is partially correct |
| 24 |
Partially correct |
69 ms |
17292 KB |
Output is partially correct |
| 25 |
Correct |
56 ms |
17424 KB |
Output is correct |
| 26 |
Correct |
3 ms |
12408 KB |
Output is correct |
| 27 |
Correct |
0 ms |
12408 KB |
Output is correct |
| 28 |
Correct |
0 ms |
12540 KB |
Output is correct |
| 29 |
Correct |
0 ms |
12540 KB |
Output is correct |
| 30 |
Correct |
3 ms |
12408 KB |
Output is correct |
| 31 |
Correct |
0 ms |
12408 KB |
Output is correct |
| 32 |
Partially correct |
0 ms |
12408 KB |
Output is partially correct |
| 33 |
Partially correct |
0 ms |
12408 KB |
Output is partially correct |
| 34 |
Correct |
0 ms |
12408 KB |
Output is correct |
| 35 |
Correct |
3 ms |
12408 KB |
Output is correct |
| 36 |
Correct |
3 ms |
12804 KB |
Output is correct |
| 37 |
Correct |
0 ms |
12672 KB |
Output is correct |
| 38 |
Correct |
9 ms |
12672 KB |
Output is correct |
| 39 |
Partially correct |
0 ms |
12672 KB |
Output is partially correct |
| 40 |
Correct |
3 ms |
12804 KB |
Output is correct |
