Submission #1248270

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

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;
            }
        }

        lg viscnt = 0; //방문한 칸의 수
        lg iscycle = 0;
        for(lg j=1;j<=m;j++){
            if(arr[i][j] == 0) continue;
            
            if(vis[i][j] == 2) break; //완전히 불가능하다.
            lg pos = 1; //이미 방문했다면 불가능한게 맞다.
            if(vis[i][j] != 0){
                pos = 0;
            }
            else{
                //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;
                    }

                    //수평 방향 이동
                    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) break; //아예 불가능함

            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