当前位置:网站首页>Sword finger offer 12 Path in matrix
Sword finger offer 12 Path in matrix
2022-07-03 12:59:00 【Hiccup~~~~】
The finger of the sword Offer 12. Path in matrix
Medium difficulty 601 Switch to English to receive dynamic feedback
Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false .
The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .
for example , In the following 3×4 The matrix of contains the word “ABCCED”( The letters in the word are marked ).
Example 1:
Input :board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output :true
Example 2:
Input :board = [["a","b"],["c","d"]], word = "abcd" Output :false
Tips :
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- board and word It consists of upper and lower case English letters only
* Ideas :
Imitate the following ideas , Clear up every time .
Ideas
Code
class Solution {
public:
bool flag=0;
bool dfs(vector<vector<char> >& board, string word,int i,int j,int k){
if(i<0||j<0||i>=board.size()||j>=board[0].size()||board[i][j]!=word[k])
return 0;
if(k==word.size()-1)
return 1;
// In four directions
board[i][j]='\0';
// prune , no need + It is ||
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;
}
bool exist(vector<vector<char> >& board, string word) {
if(word=="") return true;
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(dfs(board,word,i,j,0))
return 1;
}
}
return 0;
}
};
边栏推荐
- Powerful avatar making artifact wechat applet
- [ArcGIS user defined script tool] vector file generates expanded rectangular face elements
- 阿里 & 蚂蚁自研 IDE
- Xctf mobile--app1 problem solving
- Solve the problem of VI opening files with ^m at the end
- Glide question you cannot start a load for a destroyed activity
- Application of ncnn Neural Network Computing Framework in Orange Pi 3 Lts Development Board
- [review questions of database principles]
- Method overloading and rewriting
- 剑指 Offer 14- II. 剪绳子 II
猜你喜欢
Xctf mobile--rememberother problem solving
The upward and downward transformation of polymorphism
Integer case study of packaging
Differences between initial, inherit, unset, revert and all
[problem exploration and solution of one or more filters or listeners failing to start]
sitesCMS v3.1.0发布,上线微信小程序
Analysis of the influence of voltage loop on PFC system performance
最新版抽奖盲盒运营版
Analysis of a music player Login Protocol
Two solutions of leetcode101 symmetric binary tree (recursion and iteration)
随机推荐
Differences between initial, inherit, unset, revert and all
Analysis of a music player Login Protocol
ImportError: No module named examples. tutorials. mnist
Define a list, store n integers, and calculate the length, maximum value, minimum value and average value of the list
如何在微信小程序中获取用户位置?
Everything comes to him who waits
C graphical tutorial (Fourth Edition)_ Chapter 15 interface: interfacesamplep271
阿里 & 蚂蚁自研 IDE
Exploration of sqoop1.4.4 native incremental import feature
[problem exploration and solution of one or more filters or listeners failing to start]
最新版抽奖盲盒运营版
Two solutions of leetcode101 symmetric binary tree (recursion and iteration)
context. Getexternalfilesdir() is compared with the returned path
剑指 Offer 17. 打印从1到最大的n位数
Ten workplace rules
The latest version of lottery blind box operation version
Solve the problem of VI opening files with ^m at the end
Leetcode234 palindrome linked list
社交社区论坛APP超高颜值UI界面
Oh my Zsh + TMUX installation