Build Gates

https://www.acmicpc.net/problem/11975

11975번: Build Gates

이번 문제는 문제는 참 이해하기 쉽고, 직관적인데 반해 이걸 구현하려니

불편한 점이 한가지가 있습니다.

보통은 정점을 타고 들어가면서 flood fill을 수행해야 하는데 정점 사이를 이어서

fence를 놓는다는 점이 당황스럽기는 하나, 

이 불편함만 제거할 수 있으면 flood fill로 간단하게 해결할 수 있습니다.

메모리도 넉넉하겠다. 그냥 map을 더 잘게 쪼개서 2000 x 2000이 아니라 4000 x 4000으로 했습니다.

좀 더 여유를 줘서 4444로 했지만요.

그렇게 하면 fence 놓는 곳과 내가 직접 갈 수 있는 공간을 함께 확보할 수 있어서 문제가

쉽게 풀립니다.

아참, 그리고 중요한 건 굳이 4000 x 4000를 다 볼 필요가 없다는 거에요.

주인공이 걸음이 총 1000걸음 밖에 되지 않아서 y, x축 방향으로 최대/최소인 map만 보면서 flood fill을

수행하면 훨씬 빠르겠죠?

필요한 부분만 봅시다!

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
 
typedef long long ll;
typedef pair<int, int> pii;
char mp[4444][4444];
int cy, cx;
int min_y = 123456789, min_x = 123456789;                    // 필요한 부분만 보자, 굳이 4444 x 4444 배열을 다 볼 필요가 없다. 시간 낭비!
int max_y = -1, max_x = -1;
 
bool range(int y, int x) {
    return !(y < min_y || y > max_y || x < min_x || x > max_x);
}
 
 
void go(int dir) {                                        // 앞으로 면서 fence를 놓는 함수이다. 주인공이 움직인 곳의 최대/최소값을 함께 구한다.
    for(int i = 0; i < 2; i++) {
        mp[cy][cx] = 'x';
        cy += dy[dir], cx += dx[dir];
        min_y = min(cy, min_y);
        min_x = min(cx, min_x);
        max_y = max(max_y, cy);
        max_x = max(max_x, cx);
    }
}
 
int main() {
    FastIO;
 
    cy = 4004 / 2, cx = 4004 / 2;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'E') go(0);
        else if (c == 'W') go(1);
        else if (c == 'S') go(2);
        else go(3);
    }
 
    min_y -= 1, max_y += 1;     // 위 아래 옆으로 하나씩 여유를 더 줘서 의도치 않게 방이 나눠지지 않게 하였다.
    min_x -= 1, max_x += 1;
 
    int cnt = 0;
    for (int i = min_y; i <= max_y; i++) {                                // cnt 변수로 방의 갯수를 구하며, flood fill을 수행한다.
        for (int j = min_x; j <= max_x; j++) {
            if (mp[i][j] == 'o' || mp[i][j] == 'x') continue;
            cnt += 1;
            
            
            queue<pii> q;
            q.push({ i,j });
            mp[i][j] = 'o';
            while (!q.empty()) {
                pii f = q.front();
                q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int ny = f.first + dy[dir], nx = f.second + dx[dir];
                    if (!range(ny, nx) || mp[ny][nx] == 'x' || mp[ny][nx] == 'o') continue;
                    mp[ny][nx] = 'o';
                    q.push({ ny, nx });
                }
            }
 
 
        }
    }
 
    cout << cnt  - 1 << endl;
 
 
 
}