Submission #1248281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248281		yookwi	Sandwich (JOI16_sandwich)	C++20	100 / 100	4742 ms	26856 KiB

sandwich

#include<bits/stdc++.h>
using namespace std;
typedef long long lg;
typedef long double ld;
#define INF 500'000'000'000'000'000
#define pii pair<lg,lg>
#define ff first
#define ss second

lg n,m,k,t;
//Z는 0, N은 1
lg arr1[405][405];
lg arr2[405][405];
lg arr3[405][405];
lg arr4[405][405];

//왼쪽 방향으로 접근 1, 오른쪽 방향으로 접근 2
lg vis[405][405];
lg dfsvis[405][405];

lg ans[405][405];
lg ans1[405][405];
lg ans2[405][405];
lg ans3[405][405];
lg ans4[405][405];

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

lg pos = 0;
lg viscnt = 0;

void dfs(lg y,lg x, lg arr[405][405]){
    //현재 y와 x에 있다.
    //다음을 방문하자.
    lg dir1, dir2;

    if(arr[y][x] == 0){
        if(vis[y][x] == 1){
            // 왼쪽, 위
            dir1 = 0;
            dir2 = 3;
        }
        else{
            // 오른쪽, 아래
            dir1 = 1;
            dir2 = 2;
        }
    }
    else{
        if(vis[y][x] == 1){
            // 왼쪽, 아래 
            dir1 = 0;
            dir2 = 2;
        }
        else{
            // 오른쪽, 위
            dir1 = 1;
            dir2 = 3;
        }
    }

    lg ny1 = y + dy[dir1], nx1 = x + dx[dir1];
    lg ny2 = y + dy[dir2], nx2 = x + dx[dir2];

    if(dfsvis[ny1][nx1] == 1){
        pos = 0;
        return;
    }
    if(dfsvis[ny2][nx2] == 1){
        pos = 0;
        return;
    }

    //수평 방향 이동
    if(1 <= ny1 && ny1 <= n && 1 <= nx1 && nx1 <= m){
        if(vis[ny1][nx1] == 0){
            vis[ny1][nx1] = vis[y][x];
            viscnt++;

            dfsvis[ny1][nx1] = 1;
            dfs(ny1, nx1, arr);
            dfsvis[ny1][nx1] = 0;
        }
        else if(vis[ny1][nx1] != vis[y][x]){
            pos = 0;
            return;
        }
    }

    //수직 방향 이동
    if(1 <= ny2 && ny2 <= n && 1 <= nx2 && nx2 <= m){
        if(vis[ny2][nx2] == 0){
            vis[ny2][nx2] = (arr[ny2][nx2] == arr[y][x] ? vis[y][x] : 3 - vis[y][x]);
            viscnt++;

            dfsvis[ny2][nx2] = 1;
            dfs(ny2, nx2, arr);
            dfsvis[ny2][nx2] = 0;
        }
        else if(vis[ny2][nx2] != (arr[ny2][nx2] == arr[y][x] ? vis[y][x] : 3 - vis[y][x])){
            pos = 0;
            return;
        }
    }
}

void f(lg arr[405][405], lg ans[405][405]){
    //N이 왼쪽으로 뻣어나가는 것을 처리하자.
    for(lg i=1;i<=n;i++){
        for(lg y=1;y<=n;y++){
            for(lg x=1;x<=m;x++){
                vis[y][x] = 0;
            }
        }
        pos = 1;
        viscnt = 0;
        for(lg j=1;j<=m;j++){
            if(arr[i][j] == 0) continue; //Z라면 넘긴다.
            //현재가 방문되었다면 사이클이 존재하는 것이므로 뒤도 안된다.
            if(vis[i][j] != 0) break;

            vis[i][j] = 1;
            viscnt++;
            dfsvis[i][j] = 1;
            dfs(i, j, arr);
            dfsvis[i][j] = 0;

            if(pos == 0) break;
            ans[i][j] = viscnt;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(lg i=1;i<=n;i++){
        string s;
        cin >> s;
        for(lg j=1;j<=m;j++){
            if(s[j-1] == 'N') arr1[i][j] = 1;
        }
    }
    for(lg i=1;i<=n;i++){
        for(lg j=1;j<=m;j++){
            ans1[i][j] = INF;
            ans2[i][j] = INF;
            ans3[i][j] = INF;
            ans4[i][j] = INF;
        }
    }
    for(lg i=1;i<=n;i++){
        for(lg j=1;j<=m;j++){
            arr2[i][j] = 1-arr1[n-i+1][j];
            arr3[i][j] = 1-arr1[i][m-j+1];
            arr4[i][j] = arr1[n-i+1][m-j+1];
        }
    }
    f(arr1, ans1);
    f(arr2, ans2);
    f(arr3, ans3);
    f(arr4, ans4);
    for(lg i=1;i<=n;i++){
        for(lg j=1;j<=m;j++){
            lg curans = min({ans1[i][j], ans2[n-i+1][j], ans3[i][m-j+1], ans4[n-i+1][m-j+1]});
            if(curans == INF){
                cout <<"-1 ";
            }
            else{
                cout << curans * 2 <<" ";
            }
        }
        cout <<"\n";
    }
}

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