class Solution {
public:
bool dfs(vector<vector<char>>& square, string word, int position, int i, int j, vector<vector<bool>>& check) {
if (position == word.size()) return true;
if (square[i][j + 1] == word[position] && !check[i][j + 1]) {
check[i][j + 1] = true;
if (dfs(square, word, position + 1, i, j + 1, check)) {
return true;
} else {
check[i][j + 1] = false;
}
}
if (square[i][j - 1] == word[position] && !check[i][j - 1]) {
check[i][j - 1] = true;
if (dfs(square, word, position + 1, i, j - 1, check)) {
return true;
} else {
check[i][j - 1] = false;
}
}
if (square[i + 1][j] == word[position] && !check[i + 1][j]) {
check[i + 1][j] = true;
if (dfs(square, word, position + 1, i + 1, j, check)) {
return true;
} else {
check[i + 1][j] = false;
}
}
if (square[i - 1][j] == word[position] && !check[i - 1][j]) {
check[i - 1][j] = true;
if (dfs(square, word, position + 1, i - 1, j, check)) {
return true;
} else {
check[i - 1][j] = false;
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int row = board.size();
int line = board[0].size();
vector<vector<bool>> check(row + 2, vector<bool>(line + 2, false));
vector<vector<char>> square(row + 2, vector<char>(line + 2, '0'));
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < line + 1; j++) {
square[i][j] = board[i - 1][j - 1];
}
}
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < line + 1; j++) {
if (square[i][j] == word[0]) {
check[i][j] = true;
if (dfs(square, word, 1, i, j, check)) {
return true;
}
check[i][j] = false;
}
}
}
return false;
}
};
class Solution {
public:
int maximum = 0;
int sum = 0;
void dfs(vector<vector<int>>& square, int i, int j, vector<vector<bool>>& check) {
if (square[i][j + 1] != 0 && !check[i][j + 1]) {
check[i][j + 1] = true;
sum += square[i][j + 1];
dfs(square, i, j + 1, check);
check[i][j + 1] = false;
sum -= square[i][j + 1];
}
if (square[i][j - 1] != 0 && !check[i][j - 1]) {
check[i][j - 1] = true;
sum += square[i][j - 1];
dfs(square, i, j - 1, check);
check[i][j - 1] = false;
sum -= square[i][j - 1];
}
if (square[i + 1][j] != 0 && !check[i + 1][j]) {
check[i + 1][j] = true;
sum += square[i + 1][j];
dfs(square, i + 1, j, check);
check[i + 1][j] = false;
sum -= square[i + 1][j];
}
if (square[i - 1][j] != 0 && !check[i - 1][j]) {
check[i - 1][j] = true;
sum += square[i - 1][j];
dfs(square, i - 1, j, check);
check[i - 1][j] = false;
sum -= square[i - 1][j];
}
maximum = max(sum, maximum);
}
int getMaximumGold(vector<vector<int>>& grid) {
int row = grid.size();
int line = grid[0].size();
vector<vector<bool>> check(row + 2, vector<bool>(line + 2, false));
vector<vector<int>> square(row + 2, vector<int>(line + 2, 0));
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < line + 1; j++) {
square[i][j] = grid[i - 1][j - 1];
}
}
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < line + 1; j++) {
if (square[i][j] != 0) {
check[i][j] = true;
sum += square[i][j];
dfs(square, i, j, check);
check[i][j] = false;
sum = 0;
}
}
}
return maximum;
}
};
class Solution {
public:
int num = 0;
int row = 0;
int line = 0;
bool judge(vector<vector<bool>>& check) {
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < line + 1; j++) {
if (check[i][j] == false) return false;
}
}
return true;
}
void dfs(vector<vector<int>>& square, int i, int j, vector<vector<bool>>& check) {
if (square[i][j] == 2) {
if (judge(check)) {
num++;
}
}
if ((square[i][j + 1] == 0 || square[i][j + 1] == 2) && !check[i][j + 1]) {
check[i][j + 1] = true;
dfs(square, i, j + 1, check);
check[i][j + 1] = false;
}
if ((square[i][j - 1] == 0 || square[i][j - 1] == 2) && !check[i][j - 1]) {
check[i][j - 1] = true;
dfs(square, i, j - 1, check);
check[i][j - 1] = false;
}
if ((square[i + 1][j] == 0 || square[i + 1][j] == 2) && !check[i + 1][j]) {
check[i + 1][j] = true;
dfs(square, i + 1, j, check);
check[i + 1][j] = false;
}
if ((square[i - 1][j] == 0 || square[i - 1][j] == 2) && !check[i - 1][j]) {
check[i - 1][j] = true;
dfs(square, i - 1, j, check);
check[i - 1][j] = false;
}
}
int uniquePathsIII(vector<vector<int>>& grid) {
row = grid.size();
line = grid[0].size();
int position_row = 0;
int position_line = 0;
vector<vector<bool>> check(row + 2, vector<bool>(line + 2, false));
vector<vector<int>> square(row + 2, vector<int>(line + 2, 3));
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < line + 1; j++) {
square[i][j] = grid[i - 1][j - 1];
if (square[i][j] == 1 || square[i][j] == -1) {
if (square[i][j] == 1) {
position_row = i;
position_line = j;
}
check[i][j] = true;
}
}
}
dfs(square, position_row, position_line, check);
return num;
}
};
