Submission #126166

#	Time	Username	Problem	Language	Result	Execution time	Memory
126166		choikiwon	Sandwich (JOI16_sandwich)	C++17	100 / 100	3679 ms	7032 KiB

sandwich

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 444;

int N, M;
char G[MN][MN];
int vis[MN][MN];
int ans[MN][MN];
int cnt;

void dfs(int r, int c, int t) {
    if(vis[r][c] == 2) return;
    if(vis[r][c] == 1) {
        cnt = 1e9;
        return;
    }
    vis[r][c] = 1;
    cnt++;

    if(t) {
        if(G[r][c] == 'N') {
            if(r) dfs(r - 1, c, 1);
            if(c + 1 < M) dfs(r, c + 1, G[r][c + 1] == 'N');
        }
        else {
            if(r) dfs(r - 1, c, 1);
            if(c) dfs(r, c - 1, G[r][c - 1] == 'Z');
        }
    }
    else {
        if(G[r][c] == 'N') {
            if(r + 1 < N) dfs(r + 1, c, 0);
            if(c) dfs(r, c - 1, G[r][c - 1] == 'Z');
        }
        else {
            if(r + 1 < N) dfs(r + 1, c, 0);
            if(c + 1 < M) dfs(r, c + 1, G[r][c + 1] == 'N');
        }
    }

    vis[r][c] = 2;
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("\n");
        for(int j = 0; j < M; j++) {
            scanf("%c", &G[i][j]);
        }
    }

    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) ans[i][j] = 1e9;

    for(int i = 0; i < M; i++) {
        memset(vis, 0, sizeof(vis));
        cnt = 0;

        for(int j = 0; j < N; j++) {
            if(!vis[j][i]) dfs(j, i, 1);
            ans[j][i] = min(ans[j][i], cnt);
        }

        memset(vis, 0, sizeof(vis));
        cnt = 0;

        for(int j = N - 1; j >= 0; j--) {
            if(!vis[j][i]) dfs(j, i, 0);
            ans[j][i] = min(ans[j][i], cnt);
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(ans[i][j] >= 1e9) printf("-1 ");
            else printf("%d ", 2 * ans[i][j]);
        }
        printf("\n");
    }
}

Compilation message (stderr)

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]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
sandwich.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &G[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

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