目接口

按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

皇后问题

这道题其实就是在下国际象棋。

国际象棋的皇后是可以走上下左右和斜对角六个方向的。

所以在放置皇后时我们就要考虑一下在那个位置放入一个皇后我们才不会被攻击。

直到将所有能防止皇后的位置放好以后便返回放好皇后以后的棋盘。

3.题目接口

public:vectorvectorstringret;//存结果vectorstringboard;//开棋盘bool

rowCheak[10];bool

b。

但是b在[-n,n]。

//为了将负数下标去掉所以在左右两边都加上n:row-coln

bn-[0,2*n]//所以diagonal要开20个空间int

n;vectorvectorstring

0;in;i){board[i].append(n,.);}dfs(0);return

ret;}

n){ret.push_back(board);return;}for(int

col

0;coln;col){if(board[row][col].!rowCheak[row]!colCheak[col]!digit1[row-coln]!digit2[rowcol]){board[row][col]

Q;rowCheak[row]colCheak[col]digit1[row-coln]

digit2[rowcol]

.;rowCheak[row]colCheak[col]digit1[row-coln]

digit2[rowcol]

1.首先我们得找四个布尔类型的数组rowCheak,colCheak,digit1,digit2。

这四个布尔类型的数组分别标记的是行列左对角线右对角线。

2.然后便是递归的设计了我们可以采用一个一个的试的方法但是这样效率太低了。

所以我们便采用一行一行试的方法来设计递归函数。

dfs(0);

首先从第0行开始。

每次遍历一行每次在dfs函数里面遍历每一行的每一列。

当对应行列下标的位置不是Q并且这一个格子的行列对角线都没有被使用过便可以插入Q。

然后再遍历下一行假设这一行填下的皇后会导致得不到结果便要回溯处理。

3.当row越界的时候说明我们的皇后已经填完了在这个时候便可以返回了。

二单词搜索

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

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

2.解释

这一道题让我们做的便是在给定一个m*n大小的棋盘并且给定一个单词word的情况下让我们去在这个棋盘里面找到这个单词的每一个字母。

并且这个单词的每一个相邻字母在棋盘中还是相邻的。

3.题目接口

public:vectorvectorboolused;int

m,n;bool

board[0].size();used.resize(m);for(int

0;im;i){used[i].resize(n);}for(int

0;im;i){for(int

true;//df函数只有在将word的全部字母找到以后才能返回true。

}}return

bool

pos){if(i0||im||j0||jn||used[i][j]||board[i][j]!word[pos])

false;}if(pos

word.size()-1)//当最后一个字母也被匹配到了便可以返回true{return

true;}used[i][j]

dfs(board,i,j-1,word,pos1)||dfs(board,i,j1,word,pos1)||dfs(board,i-1,j,word,pos1)||dfs(board,i1,j,word,pos1);//在这个位置的上下左右寻找used[i][j]

false;//res可能是false所以要恢复现场调整上一层的寻找的下标return

res;}

public:vectorvectorboolused;int

m,n;bool

board[0].size();used.resize(m);for(int

0;im;i){used[i].resize(n);}for(int

0;im;i){for(int

{1,-1,0,0};//用数组和for循环来表示上下左右寻找for(int

0;k4;k){int

word[pos]!used[x][y])//只统计对的情况{used[x][y]

true;if(dfs(board,x,y,word,pos1))

return