信息奥赛题解｜LETTERS

---

🚀 题目浏览

【题目描述】

给出一个 $roe×col$ 的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。

【输入】

第一行，输入字母矩阵行数 $R$ 和列数 $S$，$1≤ R,S≤20$。

接着输出 $R$ 行 $S$ 列字母矩阵。

【输出】

最多能走过的不同字母的个数。

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

6

【原题链接】

http://ybt.ssoier.cn:8088/problem_show.php?pid=1212

http://noi.openjudge.cn/ch0205/156/

---

☘️ 题解分析

DFS

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 25;
int r, c;
char g[N][N];
int walk[4][2] = {{-1, 0},
                  {+1, 0},
                  {0,  +1},
                  {0,  -1}};
int res = 0;
set<char> st;  // set存储字符

void dfs(int s, int t) {
    // 将当前字符加入set中，并且更新res
    st.insert(g[s][t]);
    if (st.size() > res) res = st.size();

    // 根据该点进行拓展
    for (int i = 0; i < 4; i++) {
        // 拓展点坐标
        int dx = s + walk[i][0], dy = t + walk[i][1];
        // 该拓展点超出边界
        if (dx < 1 || dx > r || dy < 1 || dy > c) continue;
        // 该拓展点在边界内，且该点字符未被访问
        if (find(st.begin(), st.end(), g[dx][dy]) == st.end()) {
            st.insert(g[dx][dy]);
            dfs(dx, dy);
            st.erase(g[dx][dy]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> r >> c;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            cin >> g[i][j];

    dfs(1, 1);
    cout << res << endl;

    return 0;
}