AcWing 1111. 字母
原题链接
简单
作者:
cange
,
2021-04-16 15:41:30
,
所有人可见
,
阅读 321
#include<bits/stdc++.h>
using namespace std;
unordered_set<char> res;
char a[25][25];
int line,column;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
int sum=0;
bool check(int x,int y){
for(int i=0;i<4;i++){
int x1=x+dx[i];
int y1=y+dy[i];
if(x1>0&&x1<=line&&y1>0&&y1<=column&&res.count(a[x1][y1])==0){
return false;
}
}
return true;
}
void dfs(int x,int y){
if(check(x,y)){
sum=max(sum,(int)res.size());
return;
}
for(int i=0;i<4;i++){
int x1=x+dx[i];
int y1=y+dy[i];
if(x1>0&&x1<=line&&y1>0&&y1<=column&&res.count(a[x1][y1])==0){ //这个字符还没有访问过并且在范围内
res.insert(a[x1][y1]); //插入字符
dfs(x1,y1); //深搜下去
res.erase(a[x1][y1]);
}
}
}
int main()
{
scanf("%d %d",&line,&column);
getchar();
for(int i=1;i<=line;i++){
for(int j=1;j<=column;j++)
scanf("%c",&a[i][j]);
getchar();
}
res.insert(a[1][1]);
dfs(1,1);
cout<<sum<<endl;
return 0;
}