Acwing.1111 字母
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
char s[N][N];
unordered_map<char , bool> st; //用unordered_map定义st,可以不用把字符转变为ASCII码
int n , m , ans , d[N][N];
void dfs(int x , int y)
{
int dx[4] = {0 , 1 , 0 , -1} , dy[4] ={1 , 0 ,-1 , 0}; // 定义可以走的四个方向
for(int i = 0 ; i < 4 ; i ++)
{
int a = x + dx[i] , b = y + dy[i]; // 将点分别往四个方向上移动
if(a > 0 && b > 0 && a <= m && b <= n && !st[s[a][b]]) //判断要走到的点是否
//出界或者已经走过一样的字母
{
d[a][b] = d[x][y] + 1; //存储走过的字母个数
st[s[a][b]] = true; // 记录已走过的字母
ans = max(ans , d[a][b]); //把答案更新为已走过的最大的字母数
dfs(a , b); // 以当前点为依据 , 继续分别向四个方向拓展
st[s[a][b]] = false; // 恢复现场 , 回溯
d[a][b] = 0;
}
} // 如果四个方向都不能走,则返回
}
int main()
{
d[1][1] = 1; // 将起步字母记录为第一个字母
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
cin >> s[j][i]; // 读入字符矩阵
st[s[1][1]] = true; // 标记起步字母已走过
dfs(1 , 1); // 开始搜索
cout << ans << endl; // 输出答案
return 0;
}