제출 #1198496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198496		JooDdae	Sandwich (JOI16_sandwich)	C++20	100 / 100	4766 ms	17996 KiB

sandwich

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e6;
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int n, m, c[404][404][2], chk[404][404][2];
string s[404];

int dfs(int x, int y, int d) {
    if(chk[x][y][d]) return chk[x][y][d] == 2 ? INF : 0;
    chk[x][y][d] = 2;

    int re = 1;
    
    int D = d^2^(s[x][y]=='N');
    int xx = x+dx[d], yy = y+dy[D];
    if(0 <= xx && xx < n) re += dfs(xx, y, d);
    if(0 <= yy && yy < m) re += dfs(x, yy, D^2^(s[x][yy]=='N'));

    chk[x][y][d] = 1;
    return min(INF, re);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> s[i];

    for(int i=0;i<n;i++) {
        memset(chk, 0, sizeof chk);
        for(int j=0;j<m;j++) {
            c[i][j][0] = dfs(i, j, s[i][j] == 'N');
            if(j) c[i][j][0] += c[i][j-1][0];
        }

        memset(chk, 0, sizeof chk);
        for(int j=m-1;j>=0;j--) {
            c[i][j][1] = dfs(i, j, s[i][j] == 'Z');
            c[i][j][1] += c[i][j+1][1];
        }
    }

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            int p = min(c[i][j][0], c[i][j][1]);
            cout << (p >= INF ? -1 : p*2) << " ";
        }
        cout << "\n";
    }
}

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