oj.uz

Submission #436916

# Submission time Handle Problem Language Result Execution time Memory
436916 2021-06-25T09:08:00 Z qwerasdfzxcl Sandwich (JOI16_sandwich) C++14
0 / 100
 302 ms 964 KB 
#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
char matrix[404][404];
int visited[404][404];
int dp[404][404][2], dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1}, n, m;
 
bool valid(int x, int y){
    return ((1<=x && x<=n) && (1<=y && y<=m));
}
 
int count_visited(){
    int ret = 0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) if (visited[i][j]) ret++;
        int cnt = 0;
        if (visited[i][1]) cnt++;
        for (int j=2;j<=m;j++) if (visited[i][j] && !visited[i][j-1]) cnt++;
        assert(cnt<=1);
        if (cnt==2) assert(visited[i][1] && visited[i][m]);
        else if (cnt==1) assert(visited[i][1] || visited[i][m]);
    }
    return ret;
}
 
bool dfs(int x, int y, int c){
    if (visited[x][y]) return visited[x][y]==1e9;
    visited[x][y] = c+1;
    bool ret = 1;
    int nx1 = x+dx[c], nx2 = y+dy[c];
    if (valid(nx1, nx2)){
        ret &= dfs(nx1, nx2, c);
    }
    int d = 2;
    if (!c && matrix[x][y]=='Z') d = 3;
    if (c && matrix[x][y]=='N') d = 3;
    int nx3 = x+dx[d], nx4 = y+dy[d];
    if (valid(nx3, nx4)){
        if (d==2 && matrix[nx3][nx4]=='N') ret &= dfs(nx3, nx4, 0);
        else if (d==3 && matrix[nx3][nx4]=='Z') ret &= dfs(nx3, nx4, 0);
        else ret &= dfs(nx3, nx4, 1);
    }
    visited[x][y] = 1e9;
    return ret;
}
 
int main(){
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++){
        scanf("%s", matrix[i]+1);
        for (int j=1;j<=m;j++) dp[i][j][0] = dp[i][j][1] = 1e9;
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=1;k<=n;k++) fill(visited[k]+1, visited[k]+m+1, 0);
            if (dfs(i, j, 0)) dp[i][j][0] = count_visited()<<1;
            for (int k=1;k<=n;k++) fill(visited[k]+1, visited[k]+m+1, 0);
            if (dfs(i, j, 1)) dp[i][j][1] = count_visited()<<1;
            //printf("%d %d: %d %d\n", i, j, dp[i][j][0], dp[i][j][1]);
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            int ans = min(dp[i][j][0], dp[i][j][1]);
            if (ans==1e9) ans = -1;
            printf("%d ", ans);
        }
        printf("\n");
    }
    return 0;
}

Compilation message

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:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%s", matrix[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 302 ms 708 KB Output is correct
7 Runtime error 37 ms 964 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 302 ms 708 KB Output is correct
7 Runtime error 37 ms 964 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -