AcWing1111 - 字母
题设
给定一个 R×S 的大写字母矩阵,你的起始位置位于左上角,你可以向上下左右四个方向进行移动,但是不能移出边界,或者移动到曾经经过的字母(左上角字母看作第一个经过的字母)。
请问,你最多可以经过几个字母。
输入格式
第一行包含两个整数 R 和 S,表示字母矩阵的行和列。
接下来 R 行,每行包含一个长度为 S 的大写字母构成的字符串,共同构成字母矩阵。
输出格式
输出一个整数,表示最多能够经过的字母个数。
数据范围
1≤R,S≤20
输入样例:
1
2
3
4
3 6
HFDFFB
AJHGDH
DGAGEH
输出样例:
1
6
题解
这道题需要跟踪两个数据,一个是最多能经过的字母数量和已经经过的字母数,因为数据量不是很大,于是想到用一个set来储存已经经过的字母,其余跟dfs模版没什么区别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 25;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int r, s;
char g[N][N];
bool vis[N][N];
unordered_set<char> se;
int dfs(int x, int y) {
se.insert(g[x][y]);
int res = se.size();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < r && ny >= 0 && ny < s && !vis[nx][ny] && se.find(g[nx][ny]) == se.end()) {
vis[nx][ny] = true;
res = max(res, dfs(nx, ny));
vis[nx][ny] = false;
}
}
se.erase(g[x][y]);
return res;
}
int main() {
cin >> r >> s;
for (int i = 0; i < r; i++) scanf("%s", g[i]);
vis[0][0] = true;
printf("%d", dfs(0, 0));
return 0;
}
This post is licensed under CC BY 4.0 by the author.