word

单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格…题目描述

给定一个

单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。

同一个单元格内的字母不允许被重复使用。

输入board

[[A,B,C,E],[S,F,C,S],[A,D,E,E]],

word

[[A,B,C,E],[S,F,C,S],[A,D,E,E]],

word

[[A,B,C,E],[S,F,C,S],[A,D,E,E]],

word

回溯和剪枝设置一个函数check(i,j,k)判断从网格的下标[i][j]位置出发能不能搜索到单词word[k]...word[wordSize-1]即word中下标k开始的后缀字符串。

判断所有的check(i,j,0)只要有一个为真即为真否则为假。

对于check函数如果board[i][j]!word[k]return

false如果board[i][j]!word[k]kwordSize-1return

true否则就判断相邻的四个位置能不能搜到word[k1]...word[wordSize-1]。

要注意的是check函数中包含了多次递归调用如果是c的话参数写成传引用这样比值传递运行速度快能过。

值传递的话我试过过不了。

i代码

public://往右左下上四个方向走时行下标的变化和列下标的变化int

directions[4][2]{{0,1},{0,-1},{1,0},{-1,0}};bool

board,int

k){if(board[i][j]!word[k])return

false;else

direc0;direc4;direc){//依次往四个方向走int

newiidirections[direc][0],newjjdirections[direc][1];if(newi0newimnewj0newjnvisited[newi][newj]0){bool

flagcheck(board,m,n,visited,newi,newj,word,wordSize,k1);if(flag){return

false;}bool

nboard[0].size();vectorvectorint

i0;im;i){for(int

flagcheck(board,m,n,visited,i,j,word,wordSize,0);if(flag)return

true;}}return