MazeMaker

문제

나무가 있으면 X, 지나갈수 있으면 . 로 된 미로가 있다.

현재 위치에서 움직일땐 moveRow, moveCol 에서 선택할수 있다

moveRow = { 1 0 -1 }
moveCol = { 3 -2 5 }

row col
(+1,-3)
( 0,-2)
(-1,+5)  중 하나를 선택해 이동

미로에서 나오지 못하게 하거나, 가능한 이동거리가 길어지게 미로를 설계하려 한다.

. 중 어떤 곳이던 출구를 놓는게 가능하다

미로를 빠져나오는 사람은 최단경로로 출구를 향해 간다

미로와 시작위치, moveRow, moveCol 이 주어질 때
최대 이동횟수를 리턴하고, 나올수 없는 경우 -1 을 리턴한다

예시 입력

1)
"...",
"...",
"..."

0, 1
{1, 0, -1, 0}
{0, 1, 0, -1}

2)
"...",
"...",
"..."

0, 1
{1, 0, -1, 0, 1, 1, -1, -1}
{0, 1, 0, -1, 1, -1, 1, -1}

3)
"X.X",
"...",
"XXX",
"X.X"

0, 1
{1, 0, -1, 0}
{0, 1, 0, -1}

4)
".......",
"X.X.X..",
"XXX...X",
"....X..",
"X....X.",
"......."

5, 0
{1, 0, -1, 0, -2, 1}
{0, -1, 0, 1, 3, 0}

5)
"......."

0, 0
{1, 0, 1, 0, 1, 0}
{0, 1, 0, 1, 0, 1}

6)
"..X.X.X.X.X.X."

0, 0
{2, 0, -2, 0}
{0, 2, 0, -2}

예시 출력

3
2
-1
7
6
-1

생각의 변화

벽, 제자리

queue 에 가능성 다 넣어두고 꺼내면서 체크

• queue<int,int>
• moveRow[i], moveCal[i]

넣는다, 꺼낸다, 벽이다/도착이다, 다시 넣는다
방문한 적이 있으면 . 를 v 로 하는 것에 대해 (visited)

queue 에서 꺼낸후 더 탐색을 해야할텐데, 다른 걸 먼저 진행
queue 대신 deque

근데 방문했다가 돌아다오면 이전 히스토리는 지워야
움직인 후에 돌아오는 것 음..

모든 . 를 v 로 바꾸는건 답이 될수 없음

exit 으로 가는 가장 긴 경로를 얻기 때문에 문제가 된다

모든 . 마다 도착가능한 최소경로를 획득

시작위치에서
1) 최단경로로 가장 멀리갈수 있는 경로
2) 접근 불가능한 . 가 있는지

최단경로 가장 멀리

내 좌표를 입력해야 할까
이동을 입력해야 할까

누적되어야 m 까지 같이, push

r, c, m push

이미 적었으니 대각선이 묻힐 이유는 없음
단지 더 큰 수라면

아트

X 에 대한 고려

pseudo code

struct rcm {
    int r;
    int c;
    int m;
};

longestPath(maze, startRow, startCol, moveRow, moveCol)
    r = startRow, c = startcol, m = 0
    
    vector<vector<int>> map
    map.resize(maze.size())
    
    for e : map
        e.resize(maze[0].size())
        
    queue<rcm> q
    
    q.push(rcm{r, c, m});
    
    while !q.empty()
        rcm p = q.front();
        q.pop();
        
        r = p.r
        c = p.c
        m = p.m
        
        if map[r][c] == 0
            map[r][c] = m
        else if map[r][c] > m
            map[r][c] = m
            
        for i=0  i<moveRow.size()  i++
            if (0 <= r+moveRow[i] < maze.size && r+moveCol[i]) && (0 <= c+moveCol[i] < maze[0].size())
                if map[r+moveRow[i]][c+moveCol[i]] == 0
                    if r+moveRow[i] == startRow && c+moveCol[i] == startCol
                        
                    else
                        if maze[r+moveRow[i]][c+moveCol[i]] == '.'
                            q.push({r+moveRow[i], c+moveCol[i], m+1})
        
        res = 0
        
        for i=0  i<maze.size()  i++
            for j=0  j<maze[0].size()  j++
                if res < map[i][j]
                    res = map[i][j]
        
        r = 0
        c = 0
        
        for str : maze
            c = 0
            
            while (c = str.find('.',c)) != std::string::npos
                if map[r][c] == 0
                    if r == startRow && c == startCol
                    else
                        return -1
                
                c++
            r++
        
        return res