資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的獨特路徑 III
假設我們有一個二維網格，有 4 種類型的方塊 -
在一個方塊中，1 代表起點。將只有一個起點方塊。
在一個方塊中，2 代表終點。將只有一個終點方塊。
在一個方塊中，0 代表空方塊，我們可以走過。
在一個方塊中，-1 代表障礙物，我們無法走過。
我們需要找到從起點方塊到終點方塊的 4 個方向的行走路徑的數量，這些路徑恰好遍歷每個非障礙物方塊一次。
因此，如果輸入如下 -
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 2 | -1 |
則輸出將是 2，因為我們有以下兩條路徑：(0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1),(1,0), (2,0), (2,1), (2,2) 和 (0,0), (1,0), (2,0), (2,1), (1,1), (0,1), (0,2), (0,3), (1,3), (1,2), (2,2)。
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 dfs()，它將接收一個二維陣列 grid、i、j、ex、ey、empty 作為引數。
如果 i、j 不在 grid 的範圍內或 grid[i, j] 等於 -1，則 -
返回 0
如果 grid[i, j] 等於 2，則
當 empty 等於 -1 時返回 true
x := 0
(將 empty 減 1)
grid[i, j] := -1
初始化 k := 0，當 k < 4 時，更新 (將 k 加 1)，執行 -
nx := i + dir[k, 0]
ny := j + dir[k, 1]
x := x + dfs(grid, nx, ny, ex, ey, empty)
(將 empty 加 1)
grid[i, j] := 0
返回 x
在方法中執行以下操作 -
empty := 0
n := 行數，m := 列數
初始化 i := 0，當 i < n 時，更新 (將 i 加 1)，執行 -
初始化 j := 0，當 j < m 時，更新 (將 j 加 1)，執行 -
如果 grid[i, j] 等於 0，則
(將 empty 加 1)
否則，如果 grid[i, j] 等於 1，則 -
sx := i, sy := j
否則，如果 grid[i, j] 等於 2，則 -
ex := i, ey := j
返回 dfs(grid, sx, sy, ex, ey, 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 >= 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);
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
cout << (ob.uniquePathsIII(v));
}輸入
{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}輸出
2
187 次檢視
