oj.uz

답안 #845897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845897 2023-09-06T18:09:39 Z mickey080929 Sandwich (JOI16_sandwich) C++17
0 / 100
 1 ms 2652 KB 
#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);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 35.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 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 -