AcWing 1111. 字母
原题链接
简单
作者:
哈基咪
,
2020-09-16 19:41:03
,
所有人可见
,
阅读 474
//字母
//求最多能经过几个不同的字母(我理解是这样的)
//设置一个字母数组来判断该字母是否被走过,设置一个判重数组来确定自己不走入已经走过的方格,
//枚举顺序:到一个点,就上下左右到新的点
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_Alphat=27;
const int R=22;
const int S=22;
//做一个字母映射: A-'A'=0 所以A->0;
int Alphat[MAX_Alphat];
int st[R][S];
int r,s;
char map[R][S];
int res=0;
//定义方向向量
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int x, int y,int step)
{
// if(!st[x][y]&&!Alphat[map[x][y]-'A'])
// {
// res++;
// }
if(step>res) res=step;
//向四周扩散
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a>=0&&a<r&&b>=0&&b<s&&!st[a][b]&&!Alphat[map[a][b]-'A'])
{
st[a][b]=1;
Alphat[map[a][b]-'A']=1;
dfs(a,b,step+1);
st[a][b]=0;
Alphat[map[a][b]-'A']=0;
}
}
}
int main()
{
scanf("%d%d",&r,&s);
for(int i=0;i<r;i++)
{
cin>>map[i];
}
Alphat[map[0][0]-'A']=1;
dfs(0,0,1);
cout<<res<<endl;
return 0;
}