LC1036. Escape a Large Maze

작성일

https://leetcode.com/problems/concatenated-words/

  • 어딘가에서 배웠었던 좌표압축 문제
  • 얼렁뚱땅 코드를 썼는데 의외로 바로 풀렸다.
  • 최적해는 의외로 신기했는데, 200개의 점이니 최대 200번까지만 탐색하는 것이다. 이러면 좌표압축도 필요가 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    vector<vector<int>> grid;
    vector<int> mValue;
    vector<int> dest;
public:
    bool bound(int x, int y) { return x >= 0 && x <= mValue[0] && y >= 0 && y <= mValue[1]; }
    bool dfs(int x, int y) {
        if(grid[x][y]) return false;
        if(x == dest[0] && y == dest[1]) return true;
        grid[x][y] = 1;
        const int dx[4] = {0,0,1,-1};
        const int dy[4] = {1,-1,0,0};
        for(int i =0 ; i < 4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(bound(nx, ny) && dfs(nx,ny)) return true;
        }
        return false;
    }
        
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        blocked.push_back(source);
        blocked.push_back(target);
        for(int k = 0; k < 2; k++) {
            sort(blocked.begin(), blocked.end(), [k](vector<int>& a, vector<int>& b) {
                return a[k] < b[k];
            });
            
            blocked[0].push_back(blocked[0][k] != 0);
            for(int i = 1; i < blocked.size(); i++) {
                if(blocked[i-1][k] == blocked[i][k])
                    blocked[i].push_back(blocked[i-1][k+2]);
                else if(blocked[i-1][k]+1 == blocked[i][k])
                    blocked[i].push_back(blocked[i-1][k+2]+1);
                else
                    blocked[i].push_back(blocked[i-1][k+2]+2);
            }
            int last = blocked.back()[k+2];
            if (last == 999999)
                mValue.push_back(last);
            else
                mValue.push_back(last+1);
        }
        grid.resize(mValue[0]+1, vector<int>(mValue[1]+1));
        
        for(auto& p: blocked) {
            if (p[0] == source[0] && p[1] == source[1]) {
                source[0] = p[2], source[1] = p[3];
                continue;
            }
            if (p[0] == target[0] && p[1] == target[1]){
                dest.push_back(p[2]);
                dest.push_back(p[3]);
                continue;
            }
            grid[p[2]][p[3]] = 1;
        }
            
        return dfs(source[0], source[1]);
    }
};