从左上角做四连通 DFS，用 26 位掩码记录路径上用掉的字母，新字母才可进入；字母不重复蕴含格子不重复，故一个掩码即可替代格子访问数组。
OJ: roj
题目 ID: 1212
难度:普及-
标签:搜索DFS位运算回溯python
创建: 2026-09-29 23:49
更新: 2026-10-05 05:37
题目描述
给出一个 3 6 / HFDFFB / AJHGDH / DGAGEH，输出 6。
思路
从左上角做四连通 DFS，用 26 位掩码记录路径上已用掉的字母，目标格字母不在掩码中才可进入。字母不重复蕴含格子不重复，所以一个掩码即可替代访问数组；字母只有 26 种，搜索深度不超过 26，沿途刷新最大值即可。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:40
# update_at: 2026-10-04 11:48
import sys
BASE = 65 # 'A' 的 ASCII 码，字母编号 = 字节值 - BASE，落在 0..25
def max_distinct_letters(grid: list[bytes], rows: int, cols: int) -> int:
"""从左上角出发、每步四连通、不重复经过同种字母，能走出的最长步数。
字母表只有 26 个，所以路径长度天然被 26 卡住；用 26 位掩码记录"已经用掉
哪些字母"，目标格能否进入只取决于它的字母是否已在掩码里。因此不需要额外的
格子访问数组：同一字母不会在路径上出现两次，也就不可能回到走过的格子
（回到原格必然重字母）。
显式栈保存 (位置, 掩码, 已走长度)。进入子状态用 `mask | bit` 生成新整数再
压栈，父状态从未被修改，兄弟分支各自读到干净快照，不需要回溯时清零。
"""
best = 1
# 栈元素：一维位置、该位置字母已置位的掩码、到达该位置的路径长度
stack = [(0, 1 << (grid[0][0] - BASE), 1)]
while stack:
pos, mask, depth = stack.pop()
best = max(best, depth)
r, c = divmod(pos, cols)
# 四个方向的邻居，越界处用 None 占位，稍后统一过滤
neighbors = (
(r - 1, c) if r > 0 else None, # 上
(r + 1, c) if r + 1 < rows else None, # 下
(r, c - 1) if c > 0 else None, # 左
(r, c + 1) if c + 1 < cols else None, # 右
)
for nb in neighbors:
if nb is None:
continue
nr, nc = nb
bit = 1 << (grid[nr][nc] - BASE)
if mask & bit: # 该字母已在路径上，不能进入
continue
stack.append((nr * cols + nc, mask | bit, depth + 1))
return best
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
rows, cols = int(next(data)), int(next(data))
grid = [next(data) for _ in range(rows)] # 每行是 bytes，遍历它得到的就是各字母的字节值
print(max_distinct_letters(grid, rows, cols))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 05:37
* update_at: 2026-10-05 05:37
*/
// main.cpp：roj/1212 LETTERS。
// 从左上角出发四连通移动，路径上的字母不能重复，求最多经过多少个字母。
// 用 26 位掩码记录路径上用过的字母：字母不重复就蕴含格子不重复，不需要额外的访问数组。
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 21;
char grid[MAXN][MAXN]; // 字母矩阵，行列下标从 0 开始
ll rows; // 行数 R
ll cols; // 列数 S
ll best; // 目前找到的最长路径长度，起点自身算 1
int dr[4] = {-1, 1, 0, 0}; // 上下左右四个方向的行增量
int dc[4] = {0, 0, -1, 1}; // 上下左右四个方向的列增量
// 从 (r,c) 出发继续搜索；mask 记录路径上已用字母，depth 是当前路径长度。
void dfs(ll r, ll c, ll mask, ll depth) {
if (depth > best) {
best = depth;
}
for (int d = 0; d < 4; d++) {
ll nr = r + dr[d];
ll nc = c + dc[d];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
continue; // 越界
}
ll bit = 1LL << (grid[nr][nc] - 'A');
if (mask & bit) {
continue; // 该字母已经在路径上，不能进入
}
dfs(nr, nc, mask | bit, depth + 1); // mask|bit 是新掩码，父状态不被修改
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> rows >> cols;
for (ll i = 0; i < rows; i++) {
for (ll j = 0; j < cols; j++) {
cin >> grid[i][j];
}
}
best = 1;
dfs(0, 0, 1LL << (grid[0][0] - 'A'), 1);
cout << best << '\n';
return 0;
}