Submission #846500

#	Time	Username	Problem	Language	Result	Execution time	Memory
846500		mickey080929	Sandwich (JOI16_sandwich)	C++17	100 / 100	1574 ms	4448 KiB

sandwich

#include <bits/stdc++.h>

using namespace std;

int n, m;
int cnt;
int a[410][410];
int vis[410][410];
int chk[410][410];
int ans[410][410];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int dfs(int x, int y, int d) {
    cnt ++;
    vis[x][y] = 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] == nd) {
            if (chk[nx][ny]) continue;
            return 0;
        }
        if (vis[nx][ny] == (nd ^ 1)) return 0;
        if (!dfs(nx, ny, nd)) return 0;
    }
    chk[x][y] = 1;
    return 1;
}

int main() {
    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;
        }
    }
    memset(ans, -1, sizeof(ans));
    for (int i=1; i<=n; i++) {
        memset(vis, -1, sizeof(vis));
        memset(chk, 0, sizeof(chk));
        cnt = 0;
        for (int j=1; j<=m; j++) {
            if (!dfs(i, j, 1)) break;
            if (ans[i][j] == -1) ans[i][j] = cnt * 2;
            else ans[i][j] = min(ans[i][j], cnt * 2);
        }
    }
    for (int i=1; i<=n; i++) {
        memset(vis, -1, sizeof(vis));
        memset(chk, 0, sizeof(chk));
        cnt = 0;
        for (int j=m; j>=1; j--) {
            if (!dfs(i, j, 0)) break;
            if (ans[i][j] == -1) ans[i][j] = cnt * 2;
            else ans[i][j] = min(ans[i][j], cnt * 2);
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
}

Compilation message (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65