网格 (board):
- 单词搜索
中等
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
[
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
]
- 单词 (word): "ABCCED"
代码拆解：exist 函数
bool exist(vector<vector<char>> &board, string word) {
if (board.empty() || word.empty())
return false;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == word[0]) { // 找到首字母匹配的单元格
if (backtrack(board, word, i, j, 0)) {
return true;
}
}
}
}
return false;
}
执行步骤
遍历网格：外层循环 i 遍历行，内层循环 j 遍历列。
找到首字母匹配：当 board[i][j] == word[0] 时，调用 backtrack 函数开始回溯搜索。
示例中，找到两个匹配位置：(0,0) 和 (2,0)。
我们先从 (0,0) 开始分析。
bool backtrack(vector<vector<char>> &board, string &word, int i, int j, int index) {
// 边界检查和字符匹配检查
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ||
board[i][j] != word[index]) {
return false;
}
// 所有字符都已匹配成功
if (index == word.length() - 1) {
return true;
}
// 标记当前单元格为已访问
char temp = board[i][j];
board[i][j] = '#';
// 递归检查四个方向
bool found = backtrack(board, word, i + 1, j, index + 1) || // 下
backtrack(board, word, i - 1, j, index + 1) || // 上
backtrack(board, word, i, j + 1, index + 1) || // 右
backtrack(board, word, i, j - 1, index + 1); // 左
// 恢复当前单元格
board[i][j] = temp;
return found;
}
详细执行过程陈述：从 (0,0) 开始
backtrack(0,0,0) → A
↓ 右
backtrack(0,1,1) → B
↓ 右
backtrack(0,2,2) → C
↓ 下
backtrack(1,2,3) → C
↓ 下
backtrack(2,2,4) → E
↓ 左
backtrack(2,1,5) → D ✅
文本描述补充
> 边界检查：i=0, j=0 在网格内，且 board[0][0] == 'A' == word[0]，通过检查。
是否匹配最后一个字符：index=0，word.length()-1=5，不满足，继续。
标记当前单元格：board[0][0] 被标记为 '#'。
递归检查四个方向：
下：i+1=1, j=0，board[1][0]='S' != word[1]='B'，返回 false。
上：i-1=-1，越界，返回 false。
右：i=0, j+1=1，board[0][1]='B' == word[1]，递归调用 backtrack(0,1,1)。
左：j-1=-1，越界，返回 false。
递归调用 backtrack (0,1,1)
边界检查：i=0, j=1 在网格内，且 board[0][1] == 'B' == word[1]，通过检查。
是否匹配最后一个字符：index=1，不满足，继续。
标记当前单元格：board[0][1] 被标记为 '#'。
递归检查四个方向：
下：i+1=1, j=1，board[1][1]='F' != word[2]='C'，返回 false。
上：i-1=-1，越界，返回 false。
右：i=0, j+1=2，board[0][2]='C' == word[2]，递归调用 backtrack(0,2,2)。
左：board[0][0]='#' != word[2]='C'，返回 false。
递归调用 backtrack (0,2,2)
边界检查：i=0, j=2 在网格内，且 board[0][2] == 'C' == word[2]，通过检查。
是否匹配最后一个字符：index=2，不满足，继续。
标记当前单元格：board[0][2] 被标记为 '#'。
递归检查四个方向：
下：i+1=1, j=2，board[1][2]='C' == word[3]，递归调用 backtrack(1,2,3)。
上：i-1=-1，越界，返回 false。
右：i=0, j+1=3，board[0][3]='E' != word[3]='C'，返回 false。
左：board[0][1]='#' != word[3]='C'，返回 false。
递归调用 backtrack (1,2,3)
边界检查：i=1, j=2 在网格内，且 board[1][2] == 'C' == word[3]，通过检查。
是否匹配最后一个字符：index=3，不满足，继续。
标记当前单元格：board[1][2] 被标记为 '#'。
递归检查四个方向：
下：i+1=2, j=2，board[2][2]='E' == word[4]，递归调用 backtrack(2,2,4)。
上：board[0][2]='#' != word[4]='E'，返回 false。
右：i=1, j+1=3，board[1][3]='S' != word[4]='E'，返回 false。
左：i=1, j-1=1，board[1][1]='F' != word[4]='E'，返回 false。
递归调用 backtrack (2,2,4)
边界检查：i=2, j=2 在网格内，且 board[2][2] == 'E' == word[4]，通过检查。
是否匹配最后一个字符：index=4，不满足，继续。
标记当前单元格：board[2][2] 被标记为 '#'。
递归检查四个方向：
下：i+1=3，越界，返回 false。
上：board[1][2]='#' != word[5]='D'，返回 false。
右：i=2, j+1=3，board[2][3]='E' != word[5]='D'，返回 false。
左：i=2, j-1=1，board[2][1]='D' == word[5]，递归调用 backtrack(2,1,5)。
递归调用 backtrack (2,1,5)
边界检查：i=2, j=1 在网格内，且 board[2][1] == 'D' == word[5]，通过检查。
是否匹配最后一个字符：index=5 == word.length()-1，满足！返回 true。
回溯恢复过程
当 backtrack(2,1,5) 返回 true 后，递归调用逐层返回：
backtrack(2,2,4) 恢复 board[2][2] 为 'E'，返回 true。
backtrack(1,2,3) 恢复 board[1][2] 为 'C'，返回 true。
backtrack(0,2,2) 恢复 board[0][2] 为 'C'，返回 true。
backtrack(0,1,1) 恢复 board[0][1] 为 'B'，返回 true。
backtrack(0,0,0) 恢复 board[0][0] 为 'A'，返回 true。
最终结果
从 (0,0) 出发，成功找到路径 A → B → C → C → E → D。
exist 函数返回 true。
网格状态变化
1. 初始状态:
[['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
2. 标记 (0,0):
[['#', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
3. 标记 (0,1):
[['#', '#', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
4. 标记 (0,2):
[['#', '#', '#', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']]
5. 标记 (1,2):
[['#', '#', '#', 'E'],
['S', 'F', '#', 'S'],
['A', 'D', 'E', 'E']]
6. 标记 (2,2):
[['#', '#', '#', 'E'],
['S', 'F', '#', 'S'],
['A', 'D', '#', 'E']]
7. 标记 (2,1):
[['#', '#', '#', 'E'],
['S', 'F', '#', 'S'],
['A', '#', '#', 'E']] ✅
总结
递归回溯：通过递归尝试所有可能的路径，遇到不匹配的情况时回溯。
标记与恢复：临时标记已访问的单元格，防止重复使用，递归返回前恢复现场。
剪枝优化：一旦找到完整路径，立即终止搜索，避免不必要的计算。
这个过程展示了回溯算法如何高效地在二维网格中搜索目标单词
补充实现动画演示的HTML代码（AI生成)
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>单词搜索回溯过程可视化</title>
<script src="https://cdn.tailwindcss.com"></script>
<link href="https://cdn.jsdelivr.net/npm/font-awesome@4.7.0/css/font-awesome.min.css" rel="stylesheet">
<link href="https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&display=swap" rel="stylesheet">
<script>
tailwind.config = {
theme: {
extend: {
colors: {
primary: '#6C5CE7',
secondary: '#00CEFF',
accent: '#FC5C65',
danger: '#E55039',
dark: '#2D3436',
light: '#F7F1E3'
},
fontFamily: {
inter: ['Inter', 'sans-serif'],
},
}
}
}
</script>
<style type="text/tailwindcss">
@layer utilities {
.content-auto {
content-visibility: auto;
}
.grid-cell {
@apply w-14 h-14 flex items-center justify-center border-2 rounded-xl font-bold text-xl transition-all duration-300 shadow-md;
}
.grid-cell-start {
@apply bg-primary/20 border-primary text-primary animate-pulse;
}
.grid-cell-current {
@apply bg-accent/30 border-accent text-accent transform scale-110 z-10 animate-bounce;
}
.grid-cell-visited {
@apply bg-secondary/20 border-secondary text-secondary;
}
.grid-cell-failed {
@apply bg-danger/20 border-danger text-danger line-through;
}
.step-card {
@apply p-4 rounded-xl shadow-lg bg-white transition-all duration-300 hover:shadow-xl;
}
.step-number {
@apply inline-flex items-center justify-center w-10 h-10 rounded-full bg-primary text-white font-bold mr-3 text-lg;
}
.direction-arrow {
@apply text-xl font-bold transition-all duration-300;
}
.direction-arrow-active {
@apply text-accent scale-125;
}
.recursive-call {
@apply pl-6 border-l-4 border-primary/30 ml-4 my-2;
}
.stack-item {
@apply px-3 py-1 rounded-lg bg-primary/10 text-primary my-1 inline-block;
}
}
</style>
</head>
<body class="bg-gradient-to-br from-purple-50 to-indigo-100 min-h-screen font-inter">
<div class="container mx-auto px-4 py-8 max-w-7xl">
<header class="text-center mb-10">
<h1 class="text-[clamp(2rem,5vw,3rem)] font-bold text-transparent bg-clip-text bg-gradient-to-r from-primary to-indigo-600 mb-4">
单词搜索回溯过程可视化
</h1>
<p class="text-gray-600 max-w-2xl mx-auto text-lg">
通过动画演示回溯算法如何在二维网格中搜索目标单词 "ABCCED"
</p>
</header>
<div class="grid grid-cols-1 lg:grid-cols-3 gap-8 mb-10">
<!-- 左侧：步骤说明 -->
<div class="lg:col-span-1 space-y-6">
<div class="step-card bg-primary/10">
<div class="step-number">1</div>
<p class="text-dark">初始调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,0,0)</code></p>
<p class="mt-2 text-gray-600">检查 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]='A'</code> 是否匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[0]='A'</code></p>
</div>
<div class="step-card bg-gray-100" id="step-2">
<div class="step-number">2</div>
<p class="text-dark">匹配成功！标记当前单元格为已访问</p>
<p class="mt-2 text-gray-600">临时将 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]</code> 替换为 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">'#'</code> 防止重复访问</p>
</div>
<div class="step-card bg-gray-100" id="step-3">
<div class="step-number">3</div>
<p class="text-dark">递归检查四个方向：</p>
<ul class="ml-6 mt-2 space-y-2">
<li class="flex items-start">
<i class="fa fa-arrow-down text-gray-400 mr-2 mt-1" id="arrow-down"></i>
<span><span class="font-semibold">下：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[1][0]='S'</code>，不匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[1]='B'</code>，返回 <code class="bg-danger/20 px-1 py-0.5 rounded text-danger">false</code></span>
</li>
<li class="flex items-start">
<i class="fa fa-arrow-up text-gray-400 mr-2 mt-1" id="arrow-up"></i>
<span><span class="font-semibold">上：</span>坐标 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">(i-1,j) = (-1,0)</code> 越界，返回 <code class="bg-danger/20 px-1 py-0.5 rounded text-danger">false</code></span>
</li>
<li class="flex items-start">
<i class="fa fa-arrow-right text-gray-400 mr-2 mt-1" id="arrow-right"></i>
<span><span class="font-semibold">右：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][1]='B'</code>，匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[1]='B'</code>，递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,1,1)</code></span>
</li>
<li class="flex items-start">
<i class="fa fa-arrow-left text-gray-400 mr-2 mt-1" id="arrow-left"></i>
<span><span class="font-semibold">左：</span>坐标 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">(i,j-1) = (0,-1)</code> 越界，返回 <code class="bg-danger/20 px-1 py-0.5 rounded text-danger">false</code></span>
</li>
</ul>
</div>
<div class="step-card bg-gray-100 hidden" id="step-4">
<div class="step-number">4</div>
<p class="text-dark">递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,1,1)</code></p>
<div class="recursive-call">
<p class="mb-2"><span class="font-semibold">边界检查：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">i=0, j=1</code> 在网格内，且 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][1] == 'B' == word[1]</code></p>
<p class="mb-2"><span class="font-semibold">字符匹配：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">index=1</code>，未达到最后一个字符，继续递归</p>
<p><span class="font-semibold">标记单元格：</span>将 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][1]</code> 标记为 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">'#'</code></p>
</div>
</div>
<div class="step-card bg-gray-100 hidden" id="step-5">
<div class="step-number">5</div>
<p class="text-dark">在 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,1,1)</code> 中检查四个方向：</p>
<ul class="ml-6 mt-2 space-y-2">
<li class="flex items-start">
<i class="fa fa-arrow-down text-gray-400 mr-2 mt-1" id="arrow-down-2"></i>
<span><span class="font-semibold">下：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[1][1]='F'</code>，不匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[2]='C'</code>，返回 <code class="bg-danger/20 px-1 py-0.5 rounded text-danger">false</code></span>
</li>
<li class="flex items-start">
<i class="fa fa-arrow-up text-gray-400 mr-2 mt-1" id="arrow-up-2"></i>
<span><span class="font-semibold">上：</span>坐标越界，返回 <code class="bg-danger/20 px-1 py-0.5 rounded text-danger">false</code></span>
</li>
<li class="flex items-start">
<i class="fa fa-arrow-right text-gray-400 mr-2 mt-1" id="arrow-right-2"></i>
<span><span class="font-semibold">右：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][2]='C'</code>，匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[2]='C'</code>，递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,2,2)</code></span>
</li>
<li class="flex items-start">
<i class="fa fa-arrow-left text-gray-400 mr-2 mt-1" id="arrow-left-2"></i>
<span><span class="font-semibold">左：</span><code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]='#'</code> 已访问，返回 <code class="bg-danger/20 px-1 py-0.5 rounded text-danger">false</code></span>
</li>
</ul>
</div>
<!-- 更多步骤可以继续添加 -->
</div>
<!-- 右侧：网格可视化 -->
<div class="lg:col-span-2 bg-white rounded-2xl shadow-xl p-6 transform transition-all duration-500 hover:shadow-2xl">
<div class="flex justify-between items-center mb-6">
<h2 class="text-2xl font-bold text-transparent bg-clip-text bg-gradient-to-r from-primary to-indigo-600">
网格状态
</h2>
<div class="flex space-x-4">
<button id="restart-btn" class="px-5 py-2.5 bg-gray-200 hover:bg-gray-300 rounded-xl transition-colors flex items-center">
<i class="fa fa-refresh mr-2"></i> 重新开始
</button>
<button id="prev-btn" class="px-5 py-2.5 bg-gray-200 hover:bg-gray-300 rounded-xl transition-colors disabled:opacity-50 flex items-center">
<i class="fa fa-step-backward mr-2"></i> 上一步
</button>
<button id="next-btn" class="px-5 py-2.5 bg-gradient-to-r from-primary to-indigo-600 hover:opacity-90 text-white rounded-xl transition-all shadow-md hover:shadow-lg flex items-center">
下一步 <i class="fa fa-step-forward ml-2"></i>
</button>
</div>
</div>
<div class="flex justify-center mb-8">
<div class="text-xl font-semibold text-dark" id="current-step">步骤 1/10</div>
</div>
<!-- 网格 -->
<div class="grid grid-cols-4 gap-4 justify-center mb-10 relative">
<div class="grid-cell grid-cell-start" id="cell-0-0">A</div>
<div class="grid-cell" id="cell-0-1">B</div>
<div class="grid-cell" id="cell-0-2">C</div>
<div class="grid-cell" id="cell-0-3">E</div>
<div class="grid-cell" id="cell-1-0">S</div>
<div class="grid-cell" id="cell-1-1">F</div>
<div class="grid-cell" id="cell-1-2">C</div>
<div class="grid-cell" id="cell-1-3">S</div>
<div class="grid-cell" id="cell-2-0">A</div>
<div class="grid-cell" id="cell-2-1">D</div>
<div class="grid-cell" id="cell-2-2">E</div>
<div class="grid-cell" id="cell-2-3">E</div>
<!-- 方向箭头 -->
<div class="absolute invisible" id="direction-arrow" style="width: 30px; height: 30px; background-color: #FC5C65; clip-path: polygon(50% 0%, 0% 100%, 100% 100%); transform: rotate(90deg); z-index: 20;"></div>
</div>
<!-- 调用栈可视化 -->
<div class="bg-gray-50 rounded-xl p-4 mb-6">
<h3 class="font-bold mb-3 text-dark flex items-center">
<i class="fa fa-code mr-2 text-primary"></i> 递归调用栈
</h3>
<div id="call-stack" class="flex flex-wrap gap-2">
<div class="stack-item">backtrack(0,0,0)</div>
</div>
</div>
<!-- 当前状态 -->
<div class="bg-gradient-to-r from-primary/5 to-indigo-50 rounded-xl p-5">
<h3 class="font-bold mb-3 text-dark text-lg">当前状态</h3>
<p id="status-text" class="text-gray-700 text-lg">
正在检查 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]</code> 是否匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[0]</code>...
</p>
</div>
</div>
</div>
<!-- 单词匹配路径 -->
<div class="mt-10 bg-white rounded-2xl shadow-xl p-6">
<h2 class="text-2xl font-bold text-transparent bg-clip-text bg-gradient-to-r from-primary to-indigo-600 mb-6">
单词匹配路径
</h2>
<div class="flex flex-wrap justify-center items-center space-x-4 md:space-x-8">
<div class="w-16 h-16 rounded-full bg-primary flex items-center justify-center text-white font-bold text-2xl shadow-lg" id="path-0">A</div>
<div class="direction-arrow text-gray-400 text-2xl" id="path-arrow-1">→</div>
<div class="w-16 h-16 rounded-full bg-gray-200 flex items-center justify-center text-gray-700 font-bold text-2xl shadow-md" id="path-1">B</div>
<div class="direction-arrow text-gray-400 text-2xl">→</div>
<div class="w-16 h-16 rounded-full bg-gray-200 flex items-center justify-center text-gray-700 font-bold text-2xl shadow-md" id="path-2">C</div>
<div class="direction-arrow text-gray-400 text-2xl">→</div>
<div class="w-16 h-16 rounded-full bg-gray-200 flex items-center justify-center text-gray-700 font-bold text-2xl shadow-md" id="path-3">C</div>
<div class="direction-arrow text-gray-400 text-2xl">→</div>
<div class="w-16 h-16 rounded-full bg-gray-200 flex items-center justify-center text-gray-700 font-bold text-2xl shadow-md" id="path-4">E</div>
<div class="direction-arrow text-gray-400 text-2xl">→</div>
<div class="w-16 h-16 rounded-full bg-gray-200 flex items-center justify-center text-gray-700 font-bold text-2xl shadow-md" id="path-5">D</div>
</div>
</div>
<!-- 回溯算法说明 -->
<div class="mt-10 bg-white rounded-2xl shadow-xl p-6">
<h2 class="text-2xl font-bold text-transparent bg-clip-text bg-gradient-to-r from-primary to-indigo-600 mb-4">
回溯算法原理
</h2>
<div class="grid grid-cols-1 md:grid-cols-2 gap-6">
<div>
<h3 class="font-bold text-lg mb-3 text-primary">什么是回溯算法？</h3>
<p class="text-gray-700 mb-4">
回溯算法是一种通过尝试所有可能的路径来寻找问题解的算法。当它发现当前路径不可能得到解时，它会"回溯"到上一步，尝试其他路径。
</p>
<h3 class="font-bold text-lg mb-3 text-primary">在此问题中的应用</h3>
<p class="text-gray-700">
在单词搜索问题中，回溯算法从网格的每个单元格开始，递归地检查四个方向：上、下、左、右。如果当前单元格匹配单词的当前字符，则继续递归检查下一个字符，直到找到完整的单词或确定无法找到。
</p>
</div>
<div>
<h3 class="font-bold text-lg mb-3 text-primary">关键步骤</h3>
<ol class="list-decimal list-inside text-gray-700 space-y-2">
<li><span class="font-semibold">边界检查：</span>确保当前位置在网格内</li>
<li><span class="font-semibold">字符匹配：</span>检查当前单元格是否匹配单词的当前字符</li>
<li><span class="font-semibold">标记访问：</span>临时标记当前单元格为已访问，防止重复使用</li>
<li><span class="font-semibold">递归搜索：</span>尝试四个方向的相邻单元格</li>
<li><span class="font-semibold">恢复状态：</span>递归返回后恢复单元格的原始值</li>
</ol>
</div>
</div>
</div>
</div>
<footer class="mt-16 py-8 bg-gradient-to-r from-primary/10 to-indigo-100">
<div class="container mx-auto px-4 text-center text-gray-600">
<p>单词搜索回溯过程可视化 © 2023</p>
<p class="mt-2 text-sm">使用 Tailwind CSS 和 Font Awesome 构建</p>
</div>
</footer>
<script>
// 当前步骤
let currentStep = 1;
// 总步骤数
const totalSteps = 10;
// 单元格状态
const cells = {};
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 4; j++) {
cells[`${i}-${j}`] = document.getElementById(`cell-${i}-${j}`);
}
}
// 路径节点
const pathNodes = {};
for (let i = 0; i < 6; i++) {
pathNodes[i] = document.getElementById(`path-${i}`);
}
// 方向箭头
const directionArrow = document.getElementById('direction-arrow');
// 更新步骤显示
function updateStepDisplay() {
document.getElementById('current-step').textContent = `步骤 ${currentStep}/${totalSteps}`;
// 重置所有步骤卡片样式
document.querySelectorAll('.step-card').forEach(card => {
card.classList.remove('bg-primary/10');
card.classList.add('bg-gray-100');
card.classList.add('hidden');
});
// 显示当前步骤及之前的步骤
for (let i = 1; i <= Math.min(currentStep, 5); i++) {
const stepCard = document.getElementById(`step-${i}`);
if (stepCard) {
stepCard.classList.remove('hidden');
if (i === currentStep) {
stepCard.classList.remove('bg-gray-100');
stepCard.classList.add('bg-primary/10');
}
}
}
// 更新按钮状态
document.getElementById('prev-btn').disabled = currentStep === 1;
document.getElementById('next-btn').disabled = currentStep === totalSteps;
// 更新路径节点状态
for (let i = 0; i < 6; i++) {
if (i < currentStep - 1) {
pathNodes[i].classList.remove('bg-gray-200');
pathNodes[i].classList.add('bg-secondary');
} else if (i === currentStep - 1) {
pathNodes[i].classList.remove('bg-gray-200');
pathNodes[i].classList.add('bg-accent');
pathNodes[i].classList.add('animate-pulse');
} else {
pathNodes[i].classList.remove('bg-secondary', 'bg-accent', 'animate-pulse');
pathNodes[i].classList.add('bg-gray-200');
}
}
// 更新方向箭头
document.querySelectorAll('.direction-arrow').forEach(arrow => {
arrow.classList.remove('direction-arrow-active');
});
// 更新调用栈
updateCallStack();
// 更新状态文本和网格状态
updateStatusText();
}
// 更新调用栈
function updateCallStack() {
const callStack = document.getElementById('call-stack');
callStack.innerHTML = '';
// 根据当前步骤构建调用栈
let stackItems = [];
switch(currentStep) {
case 1:
case 2:
case 3:
stackItems = ['backtrack(0,0,0)'];
break;
case 4:
case 5:
stackItems = ['backtrack(0,0,0)', 'backtrack(0,1,1)'];
break;
case 6:
case 7:
stackItems = ['backtrack(0,0,0)', 'backtrack(0,1,1)', 'backtrack(0,2,2)'];
break;
case 8:
stackItems = ['backtrack(0,0,0)', 'backtrack(0,1,1)', 'backtrack(0,2,2)', 'backtrack(1,2,3)'];
break;
case 9:
stackItems = ['backtrack(0,0,0)', 'backtrack(0,1,1)', 'backtrack(0,2,2)', 'backtrack(1,2,3)', 'backtrack(2,2,4)'];
break;
case 10:
stackItems = ['backtrack(0,0,0)', 'backtrack(0,1,1)', 'backtrack(0,2,2)', 'backtrack(1,2,3)', 'backtrack(2,2,4)', 'backtrack(2,1,5)'];
break;
}
// 添加到DOM
stackItems.forEach((item, index) => {
const stackItem = document.createElement('div');
stackItem.className = 'stack-item';
stackItem.textContent = item;
// 高亮当前调用
if (index === stackItems.length - 1) {
stackItem.classList.add('bg-accent/20');
stackItem.classList.add('text-accent');
stackItem.classList.add('font-bold');
}
callStack.appendChild(stackItem);
});
}
// 更新状态文本
function updateStatusText() {
const statusText = document.getElementById('status-text');
directionArrow.classList.add('invisible');
// 重置所有单元格样式
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 4; j++) {
const cellId = `${i}-${j}`;
cells[cellId].classList.remove('grid-cell-current', 'grid-cell-visited', 'grid-cell-failed');
// 恢复原始值
if (i === 0 && j === 0) cells[cellId].textContent = 'A';
if (i === 0 && j === 1) cells[cellId].textContent = 'B';
if (i === 0 && j === 2) cells[cellId].textContent = 'C';
if (i === 1 && j === 2) cells[cellId].textContent = 'C';
if (i === 2 && j === 2) cells[cellId].textContent = 'E';
if (i === 2 && j === 1) cells[cellId].textContent = 'D';
}
}
switch(currentStep) {
case 1:
statusText.innerHTML = `正在检查 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]</code> 是否匹配 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">word[0]='A'</code>...`;
cells['0-0'].classList.add('grid-cell-current');
cells['0-0'].classList.remove('grid-cell-start');
break;
case 2:
statusText.innerHTML = `匹配成功！标记 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]</code> 为已访问`;
cells['0-0'].classList.remove('grid-cell-current');
cells['0-0'].classList.add('grid-cell-visited');
cells['0-0'].textContent = '#';
break;
case 3:
statusText.innerHTML = `正在检查 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">board[0][0]</code> 的四个方向：`;
cells['0-0'].classList.add('grid-cell-current');
cells['0-0'].classList.remove('grid-cell-visited');
cells['0-0'].textContent = 'A';
// 激活右侧箭头
document.getElementById('arrow-right').classList.add('direction-arrow-active');
document.getElementById('path-arrow-1').classList.add('direction-arrow-active');
// 显示方向箭头
positionDirectionArrow(0, 0, 'right');
break;
case 4:
statusText.innerHTML = `递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,1,1)</code>`;
cells['0-1'].classList.add('grid-cell-current');
cells['0-0'].classList.add('grid-cell-visited');
cells['0-0'].textContent = '#';
break;
case 5:
statusText.innerHTML = `在 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,1,1)</code> 中检查四个方向：`;
cells['0-1'].classList.add('grid-cell-current');
cells['0-0'].classList.add('grid-cell-visited');
cells['0-0'].textContent = '#';
// 激活右侧箭头
document.getElementById('arrow-right-2').classList.add('direction-arrow-active');
// 显示方向箭头
positionDirectionArrow(0, 1, 'right');
break;
case 6:
statusText.innerHTML = `递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,2,2)</code>`;
cells['0-2'].classList.add('grid-cell-current');
cells['0-1'].classList.add('grid-cell-visited');
cells['0-1'].textContent = '#';
break;
case 7:
statusText.innerHTML = `在 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(0,2,2)</code> 中检查四个方向：`;
cells['0-2'].classList.add('grid-cell-current');
cells['0-1'].classList.add('grid-cell-visited');
cells['0-1'].textContent = '#';
// 激活下侧箭头
document.getElementById('arrow-down').classList.add('direction-arrow-active');
// 显示方向箭头
positionDirectionArrow(0, 2, 'down');
break;
case 8:
statusText.innerHTML = `递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(1,2,3)</code>`;
cells['1-2'].classList.add('grid-cell-current');
cells['0-2'].classList.add('grid-cell-visited');
cells['0-2'].textContent = '#';
break;
case 9:
statusText.innerHTML = `递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(2,2,4)</code>`;
cells['2-2'].classList.add('grid-cell-current');
cells['1-2'].classList.add('grid-cell-visited');
cells['1-2'].textContent = '#';
// 显示方向箭头
positionDirectionArrow(1, 2, 'down');
break;
case 10:
statusText.innerHTML = `递归调用 <code class="bg-primary/20 px-1 py-0.5 rounded text-primary">backtrack(2,1,5)</code> - <span class="text-accent font-bold">找到最后一个字符 'D'！</span>`;
cells['2-1'].classList.add('grid-cell-current');
cells['2-2'].classList.add('grid-cell-visited');
cells['2-2'].textContent = '#';
// 显示方向箭头
positionDirectionArrow(2, 2, 'left');
// 激活所有路径箭头
document.querySelectorAll('.direction-arrow').forEach(arrow => {
arrow.classList.add('direction-arrow-active');
});
// 高亮所有路径节点
for (let i = 0; i < 6; i++) {
pathNodes[i].classList.remove('bg-gray-200', 'bg-primary');
pathNodes[i].classList.add('bg-accent');
pathNodes[i].classList.add('animate-pulse');
}
break;
}
}
// 定位方向箭头
function positionDirectionArrow(i, j, direction) {
const cell = cells[`${i}-${j}`];
const cellRect = cell.getBoundingClientRect();
const container = document.querySelector('.grid');
const containerRect = container.getBoundingClientRect();
const cellSize = cellRect.width;
const arrowSize = 30;
let top, left, rotate;
switch(direction) {
case 'right':
top = cellRect.top - containerRect.top + cellSize/2 - arrowSize/2;
left = cellRect.right - containerRect.left;
rotate = 0;
break;
case 'down':
top = cellRect.bottom - containerRect.top;
left = cellRect.left - containerRect.left + cellSize/2 - arrowSize/2;
rotate = 90;
break;
case 'left':
top = cellRect.top - containerRect.top + cellSize/2 - arrowSize/2;
left = cellRect.left - containerRect.left - arrowSize;
rotate = 180;
break;
case 'up':
top = cellRect.top - containerRect.top - arrowSize;
left = cellRect.left - containerRect.left + cellSize/2 - arrowSize/2;
rotate = 270;
break;
}
// 设置箭头位置和旋转
directionArrow.style.top = `${top}px`;
directionArrow.style.left = `${left}px`;
directionArrow.style.transform = `rotate(${rotate}deg)`;
directionArrow.classList.remove('invisible');
}
// 重新开始
function restartVisualization() {
// 重置所有状态
currentStep = 1;
// 重置路径节点
for (let i = 0; i < 6; i++) {
pathNodes[i].classList.remove('bg-secondary', 'bg-accent', 'animate-pulse');
pathNodes[i].classList.add('bg-gray-200');
}
// 重置方向箭头
document.querySelectorAll('.direction-arrow').forEach(arrow => {
arrow.classList.remove('direction-arrow-active');
});
// 更新显示
updateStepDisplay();
}
// 初始化页面
document.addEventListener('DOMContentLoaded', function() {
// 初始化显示
updateStepDisplay();
// 设置按钮事件
document.getElementById('prev-btn').addEventListener('click', function() {
if (currentStep > 1) {
currentStep--;
updateStepDisplay();
}
});
document.getElementById('next-btn').addEventListener('click', function() {
if (currentStep < totalSteps) {
currentStep++;
updateStepDisplay();
}
});
// 添加重新开始按钮事件
document.getElementById('restart-btn').addEventListener('click', restartVisualization);
// 添加键盘导航
document.addEventListener('keydown', function(e) {
if (e.key === 'ArrowLeft' && currentStep > 1) {
currentStep--;
updateStepDisplay();
} else if (e.key === 'ArrowRight' && currentStep < totalSteps) {
currentStep++;
updateStepDisplay();
} else if (e.key === 'r' || e.key === 'R') {
restartVisualization();
}
});
});
</script>
</body>
</html>