Unique Paths III

맵을 의미하는 2차원 정수형 벡터 데이터를 받는다.

입구는 1, 출구는 2, 이동 불가능한 위치는 -1, 나머지는 0으로 표시될 때,

입구에서 시작하여 이동 불가능 칸을 제외한 모든 칸을 한번씩만 밟고

출구로 나오는 경로의 개수를 구하는 문제

class Solution {
public:
    const static int MAXIMUM = 20;
    int uniquePathsIII(vector<vector<int>>& grid) {
        
        int obstacleCount{0};
        pair<int, int> start{};
        pair<int, int> end{};
        int row = grid.size();
        int col = grid[0].size();

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == 1)
                {
                    start = {i, j};
                }
                else if (grid[i][j] == 2)
                {
                    end = {i, j};
                }
                else if (grid[i][j] == -1)
                {
                    obstacleCount++;
                }
            }
        }

        int needStep{row * col - obstacleCount};
        int result{0};
        bool visited[MAXIMUM][MAXIMUM]{};
        
        visited[start.first][start.second] = true;

        SearchDFS(start, 1, visited, grid, needStep, end, result);

        return result;
    }

    static const int DIRECTION = 4;
    void SearchDFS(pair<int, int> point, int step, bool visited[][MAXIMUM], vector<vector<int>> &grid, int &needStep, pair<int, int> &end, int &result)
    {
        if (step == needStep && point.first == end.first && point.second == end.second)
        {
            result++;
            return;
        }

        static int DirectionX[DIRECTION] = {0, 0, -1, 1};
        static int DirectionY[DIRECTION] = {-1, 1, 0, 0};

        for (int i = 0; i < DIRECTION; i++)
        {
            int nextRow{point.first + DirectionY[i]};
            int nextCol{point.second + DirectionX[i]};

            if (nextRow < 0 || grid.size() <= nextRow)
            {
                continue;
            }

            if (nextCol <0 || grid.front().size() <= nextCol)
            {
                continue;
            }

            if (grid[nextRow][nextCol] == -1)
            {
                continue;
            }

            if (visited[nextRow][nextCol])
            {
                continue;
            }

            visited[nextRow][nextCol] = true;
            SearchDFS({nextRow, nextCol}, step + 1, visited, grid, needStep, end, result);
            visited[nextRow][nextCol] = false;
        }

        return;
    }
};