题目限制:
不走重复字母
思路
·dfs,传入3个参数x,y,d,表示走到(x,y)时经过的字母个数d,用全局变量ans来维护经过字母个数的最大值
·用map映射来判断子节点的字母是否走过
C++ 代码
#include<iostream>
#include<map>
using namespace std;
const int N = 20;
int r, s;
char p[N][N]; //存地图
map<char, bool>mp; //用map映射,不走重复字母
int ans = 0; //最长经过字母数
void dfs(int x, int y, int d)//走到(x,y)时经过了d个字母
{
//维护ans
ans = max(ans, d);
//开始判断下一步
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };//子节点情况
for (int i = 0; i < 4; i++)
{
int x2 = x + dx[i], y2 = y + dy[i];
if (x2 >= 0 && x2 < r && y2 >= 0 && y2 < s && !mp[p[x2][y2]])
{
//说明这个点可以走
mp[p[x2][y2]] = true; //子节点的字符打上标记
dfs(x2, y2, d + 1); //走子节点
mp[p[x2][y2]] = false; //恢复现场
}
}
}
int main()
{
cin >> r >> s;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < s; j++)
{
char c;
cin >> c;
mp[c] = false; //初始化字母表
p[i][j] = c;
}
}
mp[p[0][0]] = true; //第一个字符已经走过
dfs(0, 0, 1); //深度优先搜索
cout << ans;
return 0;
}