题目描述

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

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

样例

3 6
HFDFFB
AJHGDH
DGAGEH

6

算法

(DFS外部搜索)

1. DFS也分外部搜索和内部搜索，那么区别依然是格子和整个棋盘来分辨。这道题是个外部，因为整个棋盘的状态进行后，是不可逆的，要枚举新的状态，除了向下递归外，也可能要回溯，恢复现场，那么这样就算外部搜索。
2. 那么八皇后也是外部搜索，因为它的每一次递归，会改变棋盘本身。如果用递归超时，就剪枝。所谓的回溯就是我们的恢复现场。
3. 算法中的参数：

   • 当前走到了哪个格子，int u = g[x][y] - 'A
   • 当前路径已经包含了哪些字母，st[u] = true, st[u] = false

4. 依然用到了方向数组，将判断条件if(a >= 0 && a < r && b >= 0 && b < s)和if(!st[t])分开。
5. dfs()中的for循环的目的就是，针对当前字母u，u的4个方向，枚举每一个方向下的下一个字母t，字母u的最大长度，sum就是用来记录最大长度的，当跳出for()循环的时候，说明从字母u出发的最大长度已经找到了，最后return sum + 1，是因为u自身也算是一个长度单位。

时间复杂度

$O(3^k)$
k表示整个矩阵的元素个数，或者说字母的个数。
为什么是3呢，因为每个字母只能向3个方向上前进，不能走走过的路。

C++ 代码

#include <iostream>

using namespace std;

const int N = 30;

int r, s;
char g[N][N];
// bool st[N][N];
bool st[N];
int res;

int dfs(int x, int y)
{
    // if(x == r && y == s) return 1;
    int u = g[x][y] - 'A';
    st[u] = true;

    int sum = 0;
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];

        // if(!st[a][b] && a >= 0 && a < r && b >= 0 && b < s)
        if(a >= 0 && a < r && b >= 0 && b < s)
        {
            /*
            st[a][b] = true;
            res += dfs(a, b);
            st[a][b] = false;
            */

            int t = g[a][b] - 'A';
            if(!st[t]) sum = max(sum, dfs(a, b));
        }
    }

    st[u] = false;
    //return res;
    return sum + 1;
}

int main()
{
    cin >> r >> s;
    for(int i = 0; i < r; i ++) cin >> g[i];

    cout << dfs(0, 0) << endl;

    return 0;
}