本文主要是介绍AcWing 1111：字母 ← dfs bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目来源】
https://www.acwing.com/problem/content/1113/
【题目描述】
给定一个 R×S 的大写字母矩阵，你的起始位置位于左上角，你可以向上下左右四个方向进行移动，但是不能移出边界，或者移动到曾经经过的字母（左上角字母看作第一个经过的字母）。
请问，你最多可以经过几个字母。
【输入格式】
第一行包含两个整数 R 和 S，表示字母矩阵的行和列。
接下来 R 行，每行包含一个长度为 S 的大写字母构成的字符串，共同构成字母矩阵。
【输出格式】
输出一个整数，表示最多能够经过的字母个数。
【数据范围】
1≤R,S≤20
【输入样例】
3 6
HFDFFB
AJHGDH
DGAGEH
【输出样例】
6
【算法分析】
要注意的是，这里的 st 数组不是标记走过的格子，而是标记字母是否被访问过。
【算法代码：dfs】
#include <bits/stdc++.h>
using namespace std;int n,m;
int st[26];
int ans=-0x3f3f3f3f;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
vector<string> v;void dfs(int x,int y,int step){int idx=v[0][0]-'A';st[idx]=1;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0 && nx<n && ny>=0 && ny<m){int idx=v[nx][ny]-'A';if(st[idx]==1) continue;st[idx]=1;dfs(nx,ny,step+1);st[idx]=0;}}ans=max(ans,step);return;
}int main(){cin>>n>>m;for(int i=0;i<n;i++){string s;cin>>s;v.push_back(s);}dfs(0,0,1);cout<<ans<<endl;return 0;
}/*
in：
3 6
HFDFFB
AJHGDH
DGAGEHout:
6
*/
【算法代码：bfs】
#include <bits/stdc++.h>
using namespace std;int n,m;
int ans=-0x3f3f3f3f;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
vector<string> v;struct MAP{int x;int y;int st[26];int step;
};void bfs() {queue<MAP> Q;MAP s;memset(s.st,0,sizeof(s.st));s.st[v[0][0]-'A']=1;s.step=1;s.x=0;s.y=0;Q.push(s);while(Q.size()){MAP t=Q.front();Q.pop();ans=max(ans,t.step);for(int i=0;i<4;i++){int nx=t.x+dx[i];int ny=t.y+dy[i];if(nx>=0 && nx<n && ny>=0 && ny<m){int idx=v[nx][ny]-'A';if(t.st[idx]==1) continue;MAP next;next.x=nx;next.y=ny;next.step=t.step+1;memcpy(next.st, t.st, sizeof(t.st));next.st[idx]=1;Q.push(next);}}}
}int main() {cin>>n>>m;for(int i=0;i<n;i++){string s;cin>>s;v.push_back(s);}bfs();cout<<ans<<endl;return 0;
}/*
in：
3 6
HFDFFB
AJHGDH
DGAGEH out:
6
*/
【参考文献】
https://www.acwing.com/solution/content/15385/
这篇关于AcWing 1111：字母 ← dfs bfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
