leetcode算法题之递归--综合练习(二)

1.N皇后

N皇后

class Solution {vector<vector<string>> ret;vector<string> path;int n;bool checkCol[10],checkDig1[20],checkDig2[20];
public:vector<vector<string>> solveNQueens(int _n) {n = _n;//初始化pathpath.resize(n);for(int i=0;i<n;i++){path[i].append(n,'.');}dfs(0);return ret;}void dfs(int row){if(row == n){ret.push_back(path);return;}for(int col = 0;col<n;col++){if(!checkCol[col]&& !checkDig1[col-row+n] && !checkDig2[col+row]){path[row][col] = 'Q';checkCol[col] = checkDig1[col-row+n] = checkDig2[col+row] = true;dfs(row+1);path[row][col] = '.';checkCol[col] = checkDig1[col-row+n] = checkDig2[col+row] = false;}}}
};

2.有效的数独

有效的数独

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:bool isValidSudoku(vector<vector<char>>& board) {for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]!='.'){int num = board[i][j]-'0';if(row[i][num] || col[j][num] || grid[i/3][j/3][num]){return false;}row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}return true;}
};

3.解数独

解数独

class Solution {bool row[9][10];bool col[9][10];bool grid[3][3][10];
public:void solveSudoku(vector<vector<char>>& board) {//初始化一下row,col,grid数组for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]!='.'){int num = board[i][j]-'0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i=0;i<9;i++){for(int j=0;j<9;j++){if(board[i][j]=='.'){for(int k=1;k<=9;k++){if(!row[i][k] && !col[j][k] && !grid[i/3][j/3][k]){board[i][j] = '0'+k;row[i][k] = col[j][k] = grid[i/3][j/3][k] = true;if(dfs(board) == true) return true;board[i][j] = '.';row[i][k] = col[j][k] = grid[i/3][j/3][k] = false;}}return false;}}}return true;}
};

4.单词搜索

单词搜索

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[7][7];int m,n;
public:bool exist(vector<vector<char>>& board, string word) {m = board.size(), n = board[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board,i,j,word,1)==true) return true;vis[i][j] = false;}}}return false;}bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(pos == word.size()){return true;}for(int k=0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0 && x<m && y>=0 && y<n && !vis[x][y]&& board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,x,y,word,pos+1)) return true;vis[x][y] = false;}}return false;}
};

5.黄金矿工

黄金矿工

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};bool vis[16][16];int m,n;int ret = 0;
public:int getMaximumGold(vector<vector<int>>& grid) {//暴搜，每个点都进行一次深搜m = grid.size(),n = grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]){vis[i][j] = true;dfs(grid,i,j,grid[i][j]);vis[i][j] = false;}}}return ret;}void dfs(vector<vector<int>>& grid,int i,int j,int path){ret = max(ret,path);for(int k=0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y]!=0){vis[x][y] = true;dfs(grid,x,y,path+grid[x][y]);vis[x][y] = false;}}}
};

6.不同路径III

不同路径III

class Solution {int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};vector<vector<bool>> vis;int m,n,step;int ret;
public:int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();vis = vector<vector<bool>>(m,vector<bool>(n));int bx,by;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 0) step++;else if(grid[i][j] == 1){bx = i;by = j;}}}step += 2;vis[bx][by] = true;dfs(grid,bx,by,1);return ret;}void dfs(vector<vector<int>>& grid,int i,int j,int count){if(grid[i][j] == 2){if(count == step) ret++;return;}for(int k=0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y] && grid[x][y]!=-1){vis[x][y] = true;dfs(grid,x,y,count+1);vis[x][y] = false;}}}
};