12（79） 矩阵中的路径
给定一个 $m \times n$ 二维字符网格 $board$ 和一个字符串单词 $word$ 。如果 $word$ 存在于网格中，返回 $true$ ；否则，返回 $false$ 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false提示：
- $m == board.length$
- $n = board[i].length$
- $1 <= m, n <= 6$
- $1 <= word.length <= 15$
- $board$ 和 $word$ 仅由大小写英文字母组成
题解
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(dfs(board,word,i,j,0))return true;
}
}
return false;
}
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k){
if(i>=rows || i<0 || j>=cols || j<0 || board[i][j]!=word[k])return false;
if(k==word.size()-1)return true;
board[i][j]='\0';
bool res=dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) ||
dfs(board, word, i, j+1, k+1) || dfs(board, word, i, j-1, k+1);
board[i][j]=word[k];
return res;
}
};M13 机器人的运动范围
地上有一个m行n列的方格，从坐标 $[0,0]$ 到坐标 $[m-1,n-1]$ 。一个机器人从坐标 $[0, 0] $的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3示例 2：
输入：m = 3, n = 1, k = 0
输出：1提示：
- $1 <= n,m <= 100$
- $0 <= k <= 20$
题解
class Solution {
public:
int movingCount(int m, int n, int k) {
vector<vector<bool>> visited(m, vector<bool>(n,0));
return dfs(0,0,0,0,visited,m,n,k);
}
private:
int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visited, int m, int n, int k){
if(i>=m || j>=n || k<si+sj || visited[i][j])return 0;
visited[i][j]=true;
return 1+dfs(i+1, j, (i+1)%10!=0?si+1:si-8,sj,visited,m,n,k)+
dfs(i,j+1,si,(j+1)%10!=0?sj+1:sj-8,visited,m,n,k);
}
};38 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]限制：
1 <= s 的长度 <= 8题解
class Solution {
public:
vector<string> permutation(string s) {
dfs(s, 0);
return res;
}
private:
vector<string> res;
void dfs(string s, int x){
if(x==s.size()-1){
res.push_back(s);
return;
}
set<int> st;
for(int i=x;i<s.size();i++){
if(st.find(s[i])!=st.end())continue;//重复则剪枝
st.insert(s[i]);
swap(s[i], s[x]);//交换，将s[i]固定在x位
dfs(s, x+1);//固定x+1各字符
swap(s[i],s[x]);//恢复交换
}
}
};
