AcWing 1111. 字母
宋标 Lv5
  2022-08-18 02:30:52 2022-08-18 02:30    

题目

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

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

输入格式

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

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

输出格式

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

数据范围

输入样例：

3 6
HFDFFB
AJHGDH
DGAGEH

输出样例：

6

题解

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
40
41
42
43
#include <iostream>
#include <cstring>
#define N 21

using namespace std;

char g[N][N];
bool st[30];
int n, m;
int ans;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int dist)
{
    for (int i = 0; i < 4; ++ i) 
    {
        int a = x + dx[i], b = y + dy[i];

        if (a >= 0 && a < n && b >= 0 && b < m && !st[g[a][b] - 'A'])
        {
            st[g[a][b] - 'A'] = true;
            dfs(a, b, dist + 1);
            st[g[a][b] - 'A'] = false;
        }
        else ans = max(ans, dist);
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> g[i][j];

    st[g[0][0] - 'A'] = true;
    dfs(0, 0, 1);
    cout << ans << endl;

    return 0;
}
 评论