Submission #1248271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248271		yookwi	Sandwich (JOI16_sandwich)	C++20	0 / 100	53 ms	1900 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 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};

void f(lg arr[405][405], lg ans[405][405]){
    //N이 왼쪽으로 뻣어나가는 것을 처리하자.
    for(lg i=1;i<=n;i++){
        for(lg j=1;j<=m;j++){
            lg viscnt = 0; //방문한 칸의 수
            lg iscycle = 0;
            for(lg y=1;y<=n;y++){
                for(lg x=1;x<=m;x++){
                    vis[y][x] = 0;
                }
            }

            if(arr[i][j] == 0) continue;

            lg pos = 1; //이미 방문했다면 불가능한게 맞다.
            //bfs를 돌리자.
            vis[i][j] = 1;
            viscnt++;

            queue<pii> q;
            q.push({i,j});
            while(!q.empty()){
                lg y = q.front().ff;
                lg x = q.front().ss;
                q.pop();

                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((ny1 == i && nx1 == j) || (ny2 == i && nx2 == j)){
                    //불가능하다.
                    pos = 0;
                    break;
                }

                //수평 방향 이동
                if(1 <= ny1 && ny1 <= n && 1 <= nx1 && nx1 <= m){
                    if(vis[ny1][nx1] == 0){
                        vis[ny1][nx1] = vis[y][x];
                        viscnt++;
                        q.push({ny1, nx1});
                    }
                    else if(vis[ny1][nx1] != vis[y][x]){
                        iscycle = 1;
                        break;
                    }
                }

                //수직 방향 이동
                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++;
                        q.push({ny2, nx2});
                    }
                    else if(vis[ny2][nx2] != (arr[ny2][nx2] == arr[y][x] ? vis[y][x] : 3 - vis[y][x])){
                        iscycle = 1;
                        break;
                    }
                }
            }

            if(iscycle == 1) continue; //아예 불가능함

            if(pos == 1){
                //현재는 가능함
                ans[i][j] = min(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: 0 / 35
• Subtask 2: 0 / 65