asp网站开发环境cpu,餐饮小程序制作,wordpress添加音乐特效,上海优化网站价格1. 题目
给定一个二维网格和一个单词#xff0c;找出该单词是否存在于网格中。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board
[[…1. 题目
给定一个二维网格和一个单词找出该单词是否存在于网格中。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board
[[A,B,C,E],[S,F,C,S],[A,D,E,E]
]给定 word ABCCED, 返回 true.
给定 word SEE, 返回 true.
给定 word ABCB, 返回 false.来源力扣LeetCode 链接https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 回溯解题
class Solution {
public:bool exist(vectorvectorchar board, string word) {bool ans false;int i, j;for(i 0; i board.size(); i)for(j 0; j board[0].size(); j)dfs(board,i,j,ans,word,0);return ans;}void dfs(vectorvectorchar b, int x, int y, bool ans, string word, int idx){if(ans true)return;if(x 0 || x b.size() || y 0 || y b[0].size() || b[x][y] # || b[x][y] ! word[idx]) return;if(idx word.size()-1){if(word[idx] b[x][y])ans true;return;}char ch b[x][y];b[x][y] #;//标记走过dfs(b,x1,y,ans,word,idx1);dfs(b,x-1,y,ans,word,idx1);dfs(b,x,y1,ans,word,idx1);dfs(b,x,y-1,ans,word,idx1);b[x][y] ch; //恢复现场}
};
