解释代码 board[i][j] = (char)(-board[i][j]); // word[p] 被 board[i][j] 匹配,开始向四周搜索 word[p+1..] dfs(board, i + 1, j, word, p + 1); dfs(board, i, j + 1, word, p + 1); dfs(board, i - 1, j, word, p + 1); dfs(board, i, j - 1, word, p + 1); board[i][j] = (char)(-board[i][j]); } }
时间: 2023-05-30 08:02:54 浏览: 44
这段代码是在回溯搜索中用来标记已经访问过的位置的。board[i][j]表示当前位置的状态,如果是已经访问过的,就将其取反,即从正数变为负数。这样在回溯时,就可以通过判断board[i][j]的正负来确定是否已经访问过该位置。
接下来的四行代码是在进行搜索,即向四周扩展搜索word的下一位。搜索完成后,需要将board[i][j]的状态还原,即再将其取反一次,从负数变回正数。
总之,这段代码的作用是在回溯搜索中标记已经访问过的位置,并在搜索完成后还原状态,以便下一次搜索。
相关问题
使用c sharp代码解决如下问题 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 例如,在下面的 3×4 的矩阵中包含单词 "ABCCED"(单词中的字母已标出)。 示例 1: 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出:true 示例 2: 输入:board = [["a","b"],["c","d"]], word = "abcd" 输出:false 提示: m == board.length n = board[i].length 1 <= m, n <= 6 1 <= word.length <= 15 board 和 word 仅由大小写英文字母组成
这是一个算法问题,可以使用深度优先搜索(DFS)来解决。具体操作是从每一个字符开始,分别以它们为起点进行 DFS 搜索,如果搜索到的字符串和目标字符串匹配,则返回 true,否则返回 false。代码如下:
```
public class Solution {
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 方向数组
public bool Exist(char[][] board, string word) {
int m = board.Length, n = board[0].Length;
bool[][] visited = new bool[m][];
for (int i = 0; i < m; i++) {
visited[i] = new bool[n]; // 初始化 visited 数组
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word[0] && DFS(board, visited, word, i, j, 0)) {
return true; // 找到目标字符串
}
}
}
return false; // 没有找到目标字符串
}
private bool DFS(char[][] board, bool[][] visited, string word, int r, int c, int index) {
if (index == word.Length - 1) { // 遍历到目标字符串的最后一个字符,说明找到了
return true;
}
visited[r][c] = true; // 标记当前位置为已访问
for (int i = 0; i < 4; i++) { // 搜索相邻字符
int newRow = r + direction[i][0];
int newCol = c + direction[i][1];
if (newRow < 0 || newRow >= board.Length || newCol < 0 || newCol >= board[0].Length
|| board[newRow][newCol] != word[index + 1] || visited[newRow][newCol]) {
continue; // 判断越界,字符是否匹配,是否已访问
}
if (DFS(board, visited, word, newRow, newCol, index + 1)) {
return true; // 找到目标字符串,返回 true
}
}
visited[r][c] = false; // 回溯,标记当前位置为未访问
return false;
}
}
```
C++ Boggle 代码
以下是一个简单的 C++ 实现,使用了递归和回溯法来解决 Boggle 游戏问题。该算法基于深度优先搜索和字典树(Trie)结构。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define M 3
#define N 3
#define MAX_WORD_LEN 10
// Trie 节点
struct TrieNode {
bool endOfWord; // 是否是单词的结尾
TrieNode* children[26]; // 每个节点最多有 26 个子节点
};
// 创建一个新的 Trie 节点
TrieNode* getTrieNode() {
TrieNode* node = new TrieNode;
node->endOfWord = false;
for (int i = 0; i < 26; i++) {
node->children[i] = nullptr;
}
return node;
}
// 将单词插入到 Trie 中
void insert(TrieNode* root, string word) {
TrieNode* curr = root;
for (int i = 0; i < word.length(); i++) {
int index = word[i] - 'a';
if (curr->children[index] == nullptr) {
curr->children[index] = getTrieNode();
}
curr = curr->children[index];
}
curr->endOfWord = true;
}
// 检查 Trie 中是否存在给定单词
bool search(TrieNode* root, string word) {
TrieNode* curr = root;
for (int i = 0; i < word.length(); i++) {
int index = word[i] - 'a';
if (curr->children[index] == nullptr) {
return false;
}
curr = curr->children[index];
}
return curr->endOfWord;
}
// 检查给定坐标是否在矩阵内部
bool isSafe(int i, int j) {
return (i >= 0 && i < M && j >= 0 && j < N);
}
// 在 Boggle 矩阵中搜索单词
void searchWord(vector<vector<char>>& board, int i, int j, TrieNode* root, set<string>& words, string currWord) {
// 检查当前单词是否在 Trie 树中存在
if (search(root, currWord)) {
words.insert(currWord);
}
// 检查相邻的 8 个单元格,以确定下一个字符
int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
for (int k = 0; k < 8; k++) {
int ni = i + x[k];
int nj = j + y[k];
// 如果坐标在矩阵内部且未被访问过,则递归搜索
if (isSafe(ni, nj) && board[ni][nj] != '#' && board[ni][nj] != '*') {
char temp = board[ni][nj];
board[ni][nj] = '*';
searchWord(board, ni, nj, root->children[temp - 'a'], words, currWord + temp);
board[ni][nj] = temp;
}
}
}
// 打印所有找到的单词
void printWords(set<string>& words) {
for (auto word : words) {
cout << word << " ";
}
cout << endl;
}
// 主函数
int main() {
vector<vector<char>> board = { {'g', 'i', 'z'},
{'u', 'e', 'k'},
{'q', 's', 'e'} };
set<string> words;
// 建立 Trie 树
TrieNode* root = getTrieNode();
insert(root, "geek");
insert(root, "quiz");
insert(root, "seek");
insert(root, "guiz");
insert(root, "size");
// 在矩阵中搜索所有可能的单词
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
char c = board[i][j];
if (root->children[c - 'a'] != nullptr) {
string currWord = "";
currWord += c;
board[i][j] = '*';
searchWord(board, i, j, root->children[c - 'a'], words, currWord);
board[i][j] = c;
}
}
}
// 打印所有找到的单词
printWords(words);
return 0;
}
```
在上面的代码中,我们首先构建了一个 Trie 树,然后使用深度优先搜索和回溯法来搜索 Boggle 矩阵中的所有可能单词。在搜索过程中,我们检查当前单元格的相邻单元格,并使用 Trie 树来确定下一个字符是否存在于单词中。如果是,则继续向下搜索;否则,我们回溯到先前的状态并尝试其他路径。最后,我们打印所有找到的单词。