#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[410][410];
int vis[410][410];
int chk[410][410];
int dp[410][410][2];
int num = 0;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int dfs(int x, int y, int d) {
if (!dp[x][y][d]) return 0;
vis[x][y] = num << 1 | d;
for (int i=0; i<2; i++) {
int t = (d<<1) + a[x][y] + i; if (t >= 4) t -= 4;
int nx = x + dx[t];
int ny = y + dy[t];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
int nd = (t >= a[nx][ny] && t <= 1+a[nx][ny]) ^ 1;
if (vis[nx][ny] == (num << 1 | nd)) {
if (chk[nx][ny] == num) continue;
return dp[x][y][d] = 0;
}
if (vis[nx][ny] == (num << 1 | nd ^ 1)) return dp[x][y][d] = 0;
if (!dfs(nx, ny, nd)) return dp[x][y][d] = 0;
}
chk[x][y] = num;
return 1;
}
int solve(int sx, int sy, int sd) {
num ++;
if (!dfs(sx, sy, sd)) return -1;
int ans = 0;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
ans += (vis[i][j] >= (num << 1));
}
}
return ans << 1;
}
int main() {
memset(dp, 1, sizeof(dp));
scanf("%d %d", &n, &m);
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
char c;
scanf(" %c", &c);
if (c == 'N') a[i][j] = 0;
else a[i][j] = 1;
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
int t1 = solve(i, j, 0), t2 = solve(i, j, 1);
if (t1 == -1) printf("%d ", t2);
else if (t2 == -1) printf("%d ", t1);
else printf("%d ", min(t1, t2));
}
printf("\n");
}
}
Compilation message
sandwich.cpp: In function 'int dfs(int, int, int)':
sandwich.cpp:28:43: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
28 | if (vis[nx][ny] == (num << 1 | nd ^ 1)) return dp[x][y][d] = 0;
| ~~~^~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
