คำอธิบายโจทย์
กริด 2D: 1=start, 2=end, 0=ว่าง, -1=อุปสรรค หาเส้นทาง 4 ทิศทางจาก start ถึง end เดินครบทุกช่องว่างทีละ 1 ครั้ง
ตัวอย่าง
Grid 3×4 → Output: 2
พบ 2 เส้นทางที่ครอบคลุมทุกช่อง 0 ทีละ 1 ครั้ง
วิธีแก้ปัญหา
DFS + Backtracking:
- นับช่องว่าง (empty) รวม start
- DFS จาก start mark visited = -1
- ถึง end: ถ้า empty==-1 (เดินครบทุกช่อง) → count++
- Backtrack: unmark, empty++
การทำงานของโค้ด
#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<0 || i>=grid.size() || j<0 || j>=grid[0].size() || 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 ni=i+dir[k][0], nj=j+dir[k][1];
x += dfs(grid, ni, nj, ex, ey, empty);
}
empty++; grid[i][j]=0;
return x;
}
int uniquePathsIII(vector<vector<int>>& grid) {
int empty=0, sx, sy, ex, ey;
int n=grid.size(), m=grid[0].size();
for(int i=0;i
อินพุต
{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}
เอาต์พุต
2
