Đường đi duy nhất III trong C++

Cho lưới 2D với 4 loại ô: 1=điểm bắt đầu (duy nhất), 2=điểm kết thúc (duy nhất), 0=ô trống, -1=chướng ngại. Tìm số đường đi 4 hướng từ start đến end đi qua TẤT CẢ ô không phải chướng ngại ĐÚNG 1 LẦN.

Ví dụ: lưới 3x4, start(0,0), end(2,2). Có 2 đường đi hợp lệ.

Giải pháp

DFS backtracking với đếm ô trống:

• Đếm số ô trống (empty), tìm start (sx,sy) và end (ex,ey)
• DFS(grid, i, j, ex, ey, empty):
  • Nếu ngoài lưới hoặc ô -1: trả về 0
  • Nếu đến end: trả về 1 nếu empty==-1 (đã đi hết), ngược lại 0
  • Đánh dấu ô hiện tại = -1, empty--
  • Đệ quy 4 hướng, cộng kết quả
  • Backtrack: khôi phục ô = 0, empty++
  • Trả về tổng
• Gọi DFS từ start, trả về kết quả

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; 

class Solution { 
public: 
    int dfs(vector<vector<int> >& grid, int i, int j, int ex, int ey, int empty) { 
        if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0 || grid[i][j] == -1) 
            return 0; 
        if (grid[i][j] == 2) 
            return empty == -1; 
        
        int x = 0; 
        empty--; 
        grid[i][j] = -1; 
        
        for (int k = 0; k < 4; k++) { 
            int nx = i + dir[k][0]; 
            int ny = j + dir[k][1]; 
            x += dfs(grid, nx, ny, ex, ey, empty); 
        } 
        
        empty++; 
        grid[i][j] = 0; 
        return x; 
    } 
    
    int uniquePathsIII(vector<vector<int> >& grid) { 
        int empty = 0; 
        int sx, sy, ex, ey; 
        int n = grid.size(); 
        int m = grid[0].size(); 
        
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (grid[i][j] == 0) empty++; 
                else if (grid[i][j] == 1) { sx = i; sy = j; } 
                else if (grid[i][j] == 2) { ex = i; ey = j; } 
            } 
        } 
        return dfs(grid, sx, sy, ex, ey, empty); 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}}; 
    cout << (ob.uniquePathsIII(v)); 
    return 0; 
}

Đầu vào

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

Đầu ra

2