目录
力扣37.解数独
我开始没有想到这个三维数组判断，我开始是写了9个if,else，然后发现太麻烦，过于奇怪了，去看了一眼题解，他并没有看具体里面的数组，而是把她分成一个大块，9个大块，统计一个大块之后，不去细节的遍历具体哪9个小块
class Solution {
boolean row[][];
boolean col[][];
boolean grid[][][];
public boolean dfs(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]){
row[i][k]=col[j][k]=grid[i/3][j/3][k]=true;
board[i][j]=(char)('0'+k);
//我需要知道当前层的情况，假如是正确，那么要返回，不然假如他说错误的就需要返回，那么他会到最后一层一直都返回true,再一直返回回来。
if(dfs(board)==true) return true;
board[i][j]='.';
row[i][k]=col[j][k]=grid[i/3][j/3][k]=false;
}
}
//假如每个都无法填写，就直接返回false;因为这个填写不正确，可能是上一个的错误
return false;
}
}
}
return true;
}
public void solveSudoku(char[][] board) {
row=new boolean[9][10];
col=new boolean[9][10];
grid=new boolean[3][3][10];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
//在这里检查是否有数字
int num=board[i][j]-'0';
if(num>=1&&num<=9){
//统计当前的所有数字，并且给他对应的行列，9个大块进行标记
row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
}
}
}
dfs(board);
}
}力扣79.单词搜索
单词搜索，我的想法开始是用bfs，为啥不用勒，是因为bfs俺会，嘿嘿，所以试试dfs,但是dfs实际内层还是bfs的核心
class Solution { char[]word; int n; int m; boolean[][]vis; int[]dx={0,0,1,-1}; int[]dy={1,-1,0,0}; Queue<int[]>q; //k表示当前到第几个字母了 public boolean dfs(char[][]board,int k){ if(k>=word.length){return true;} while(!q.isEmpty()){ int sz=q.size(); while(sz!=0){ int[]t=q.poll(); for(int i=0;i<4;i++){ int x=dx[i]+t[0]; int y=dy[i]+t[1]; if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==false&&board[x][y]==word[k]){ q.add(new int[]{x,y}); vis[x][y]=true; if (dfs(board,++k)==true)return true; k--; vis[x][y]=false; } } sz--; } } if(q.isEmpty()&&k<word.length)return false; return true; } public boolean exist(char[][] board, String words) { word=words.toCharArray(); q=new LinkedList<>(); n=board.length; m=board[0].length; vis=new boolean[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(board[i][j]==word[0]){ q.add(new int[]{i,j}); vis[i][j]=true; if(dfs(board,1)==true)return true; vis[i][j]=false; } } } return false; } }
力扣1219.黄金矿工
class Solution {
int []dx={0,0,1,-1};
int []dy={1,-1,0,0};
int n;
int m;
int ret=0;
int sum;
boolean[][]vis;
Queue<int[]>q=new LinkedList<>();
public int dfs(int[][] grid){
while(!q.isEmpty()){
int sz=q.size();
while(sz!=0){
int[]t=q.poll();
for(int i=0;i<4;i++){
int x=t[0]+dx[i];
int y=t[1]+dy[i];
if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==false&&grid[x][y]!=0){
sum+= grid[x][y];
q.add(new int[]{x,y});
vis[x][y]=true;
ret =Math.max(dfs(grid),ret);
sum-= grid[x][y];
vis[x][y]=false;
}
}
sz--;
}
}
return sum;
}
public int getMaximumGold(int[][] grid) {
n=grid.length;
m=grid[0].length;
vis=new boolean[n][m];
int max=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]!=0){
q.add(new int[]{i,j});
vis[i][j]=true;
sum+=grid[i][j];
//这里正常来说是不用这个比较一下，但是在第54个用例的时候，发现有一个是单个的最大，一个最大34，一个最大38，他是加在sum这里的
ret=Math.max(ret,sum);
dfs(grid);
max=Math.max(max,ret);
sum-=grid[i][j];
vis[i][j]=false;
}
}
}
return max;
}
}力扣980.不同路径III
版本1基于bfs的dfs，他的意思是说用一个队列来存储每一步的点，然后假如不满足条件，就回退到上一步，然后再去给他操作，这个时间比下面的要慢，主要是因为这个他的再每次到达2之后，都要去遍历一下这个vis数组，看看是不是都走完了。
class Solution {
int m,n;
boolean [][]vis;
int[]dx={0,0,1,-1};
int[]dy={1,-1,0,0};
int ret,max;
Queue <int[]>q=new LinkedList<>();
public int uniquePathsIII(int[][] grid) {
n=grid.length;
m=grid[0].length;
vis=new boolean[n][m];
for(int i=0;i<n;i++) {
//我把不能走的都定为true,这样就全部是 true了最后
for (int j = 0; j < m; j++) {
if ( grid[i][j] == -1) {
vis[i][j] = true;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]==1){
q.add(new int[]{i,j});
vis[i][j]=true;
dfs(grid);
}
}
}
return max;
}
public boolean dfs(int[][] grid) {
while(!q.isEmpty()){
int sz=q.size();
while(sz>0){
int[]t=q.poll();
if(grid[t[0]][t[1]]==2){
for(int k=0;k<n;k++){
for(int j=0;j<m;j++){
if(vis[k][j]!=true) return false;
}
}
ret++;
max=Math.max(max,ret);
return true;
}
for(int i=0;i<4;i++){
int x=t[0]+dx[i];
int y=t[1]+dy[i];
if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==false&&(grid[x][y]==0||grid[x][y]==2)){
q.add(new int[]{x,y});
vis[x][y]=true;
dfs(grid);
vis[x][y]=false;
}
}
sz--;
}
}
return true;
}
}dfs这个就没有队列，相当于是自己一个一个进，同时我们是传递当前节点，以及他的思路就是统计可以走的点，最后的点数够这个数目，就说明这个路径可以
class Solution {
int m,n,step;
int ret=0;
boolean[][]vis;
static int[]dx={0,0,1,-1};
static int[]dy={1,-1,0,0};
public int uniquePathsIII(int[][] grid) {
n=grid.length;
m=grid[0].length;
vis=new boolean[n][m];
int bx=0;
int by=0;
//统计了所有0的个数，和所有的起点
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]==0) step++;
else if(grid[i][j]==1){
bx=i;
by=j;
}
}
}
//统计开始的1和结束的2，所以需要加等2
step+=2;
vis[bx][by]=true;
dfs(grid,bx,by,1);
return ret;
}
public void dfs(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];
int y=j+dy[k];
if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&grid[x][y]!=-1){
vis[x][y]=true;
dfs(grid,x,y,count+1);
vis[x][y]=false;
}
}
}
}