题目描述

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

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

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

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

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

数据范围
1≤R,S≤20

输入样例

3 6
HFDFFB
AJHGDH
DGAGEH

输出样例

6

算法1

DFS

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25;

int n, m, ans;

char g[N][N];

bool visited[30];

void dfs(int x, int y, int u)
{
    if (x < 0 || x >= n || y < 0 || y >= m || visited[g[x][y] - 'A'])
    {
        ans = max(ans, u);
        return;
    }

    visited[g[x][y] - 'A'] = true;
    dfs(x + 1, y, u + 1);
    dfs(x - 1, y, u + 1);
    dfs(x, y + 1, u + 1);
    dfs(x, y - 1, u + 1);
    visited[g[x][y] - 'A'] = false;
}

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

    dfs(0, 0, 0);

    cout << ans << endl;

    return 0;
}