제출 #1248271

#제출 시각아이디문제언어결과실행 시간메모리
1248271yookwiSandwich (JOI16_sandwich)C++20
0 / 100
53 ms1900 KiB
#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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...