一：单词搜索

题目：

给定一个m*n的二位字符网格和一个字符串单词。如果单词存在于网格中，返回true，不然，返回false。

注意：单词必须按照字母顺序，通过相邻的单元格内的字母构成，同一个单元格内的字母不可以被重复使用。

方法：

1：画出决策树

2：算法原理

dfs函数的设计：

dfs(board,i,j,s,pos)

（board表示题给的网格，i，j表示当前的位置，s表示要查找的单词，pos表示当前查找到的位置）

细节部分：

为了避免查找当同一位置的字母，有两种方法可以解决：

（1）创建一个与网格同等大小的数组，标记每个位置是否已被使用

bool check[][];

（2）将已经用过的位置里的字母进行篡改（该种方法只适用于原数组可以被修改的情况）

特殊方法：

利用向量的方式，定义上下左右四个位置

首先，设立两个数组：int dx[4] = {0,0,1,-1}；int dy[4] = {-1,1,0,0}

将这当前位置的坐标分别加上这两个数组进行的遍历，就可以轻松得到当前位置上下左右四个位置的坐标

class Solution {bool check[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]){check[i][j] = true;if(dfs(board,i,j,word,1))  return true;check[i][j] = false;}}}return false;}int dx[4] = {0,0,-1,1};int dy[4] = {1,-1,0,0};bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(pos == word.size())return true;//1//向量的方式，定义上下左右四个位置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&&!check[x][y]&&board[x][y]==word[pos]){check[x][y] = true;if(dfs(board,x,y,word,pos+1))  return true;check[x][y] = false;}}return false;}
};

二：黄金矿工（与单词搜索思路基本一致）

题目：

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

（1）每当矿工进入一个单元，就会收集该单元格中的所有黄金。

（2）矿工每次可以从当前位置向上下左右四个方向走。

（3）每个单元格只能被开采（进入）一次。

（4）不得开采（进入）黄金数目为 0 的单元格。

（5）矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

方法：

1：画出决策树（与上一题基本一致，为避免重复，在此省略）

2：算法原理

与上一题的单词搜索思路基本一致，防止重复的方法变为了要将原先的单元格进行改变

dfs函数的设计：

void dfs(grid,i,j,path)（（i,j）为当时位置的坐标，path记录每一步走到的值并把它加起来）

PS：不需要递归出口，用一个函数将ret与path进行比较得到最大的那个即可

class Solution {bool vis[16][16];int ret;//记录最后采集到的矿石int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int m,n;
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]!=0){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]){vis[x][y] = true;dfs(grid,x,y,path+grid[x][y]);vis[x][y] = false;}}}
};

三：不同路径3

题目：

在二维网格 grid 上，有 4 种类型的方格：

（1）1 表示起始方格。且只有一个起始方格。

（2）2 表示结束方格，且只有一个结束方格。

（3）0 表示我们可以走过的空方格。

（4）-1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

方法：

1：画出决策树（与前面的思路基本一致）

2：算法原理

直接进行暴力搜索，计数到2的步数，与原本网格中0的个数进行比较，合法就直接算作一条有效路径，不合法直接返回即可

class Solution {bool vis[21][21];int dx[4] = {1,-1,0,0};int dy[4] = {0,0,1,-1};int ret;int m,n,step;
public:int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();int bx = 0,by = 0;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;}}}
};