AcWing1111 - 字母

题设

给定一个 R×S 的大写字母矩阵，你的起始位置位于左上角，你可以向上下左右四个方向进行移动，但是不能移出边界，或者移动到曾经经过的字母（左上角字母看作第一个经过的字母）。

请问，你最多可以经过几个字母。

输入格式

第一行包含两个整数 R 和 S，表示字母矩阵的行和列。

接下来 R 行，每行包含一个长度为 S 的大写字母构成的字符串，共同构成字母矩阵。

输出格式

输出一个整数，表示最多能够经过的字母个数。

数据范围

1≤R,S≤20

输入样例：

3 6
HFDFFB
AJHGDH
DGAGEH

输出样例：

6

题解

这道题需要跟踪两个数据，一个是最多能经过的字母数量和已经经过的字母数，因为数据量不是很大，于是想到用一个set来储存已经经过的字母，其余跟dfs模版没什么区别。

#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;
}