AcWing 1111. 字母
原题链接
简单
作者:
Ton_3
,
2023-11-13 17:44:27
,
所有人可见
,
阅读 69
C++ 代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=1111;
int n,m,res;
char mp[N][100];
bool st[N];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
void dfs(int x,int y,int cnt){ //类似迷宫、矩阵问题 dfs往往使用x、y坐标作为参数传递
res=max(res,cnt); //cnt既代表这条路径目前有几种不同的字母
if(res ==26) return ;
for(int i=0;i<4;i++){
int l=x+dx[i],r=y+dy[i]; //dx dy为坐标偏移量,每次移动四次遍历i=0:dx=1,dy=0,向右移动。
if(l>=0&&l<n&&r>=0&&r<m&&!st[mp[l][r]]){ //i=1: dx=0,dy=1,向上移动。
st[mp[l][r]]=true; //i=2: dx=-1,dy=0, 向左移动。
dfs(l,r,cnt+1); //l、r代表更新字母的坐标 //i=3: dx=0, dy=-1 向下移动。
st[mp[l][r]]=false;
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>mp[i];
}
st[mp[0][0]]=true;
dfs(0,0,1);
cout<<res<<endl;
}