LETTERS(DFS)

【题目描述】

给出一个row×colrow×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。

【输入】

第一行，输入字母矩阵行数RR和列数SS，1≤R,S≤201≤R,S≤20。

接着输出RR行SS列字母矩阵。

【输出】

最多能走过的不同字母的个数。

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

6

原题链接：信息学奥赛一本通（C++版）在线评测系统

学习链接：《信息学奥赛一本通》搜索与回溯算法：1212LETTERS_哔哩哔哩_bilibili

【解题思路】

1. 输入字母矩阵
2. 从左上角作为第一步，开始对其上下左右四个方向开始搜索，若四个方向都已无法搜素或搜索完毕，则回溯 
3. 直到所有路径全部搜索完毕，找到最长的路径（不能出现相同字母）

代码如下：

#include<bits/stdc++.h>
using namespace std;
int r,s;
char ch[25][25];//输入的字母矩阵 
int t[200];//桶，装入已访问的字母 
int x[4]={-1,1,0,0};//x方向的偏移量
int y[4]={0,0,-1,1};//y方向的偏移量
int maxx=0;//记录最长路径void dfs(int nx,int ny,int len)
{maxx=max(maxx,len);//每到一个字母都比较一下路径 for(int i=0;i<4;i++){//下一个出发搜索的字母坐标 int x1=nx+x[i];int y1=ny+y[i];//超出边界，跳过 if(x1<0 || x1>=r || y1<0 || y1>=s)continue;//如果该位置的字母未装入过进桶t[]，则可从该位置出发搜索 if(t[ch[x1][y1]-'A']==0){t[ch[x1][y1]-'A']=1;//将该位置的字母装入桶里//步数要+1len++;//从该点出发继续向其四个符合条件的方向搜索dfs(x1,y1,len);//从该点出发的四个方向能到达的路径都已搜索完毕，回溯回来，并将搜索留下的痕迹清理干净//首先是路径要缩短回来len--;//再将该方向得的字母移出桶外，因为其他路径的搜索可能也会经过该字母t[ch[x1][y1]-'A']=0;//将继续从其他方向的字母出发搜索，即for的i++ } }
}int main()
{cin>>r>>s;for(int i=0;i<r;i++)for(int j=0;j<s;j++)cin>>ch[i][j]; t[ch[0][0]-'A'] =1;  //注意要先将起点装入桶,避免它其他方向的字母跟他一样 dfs(0,0,1);//dfs(x,y,len);从（1，1）出发，步数len为1cout<<maxx<<endl;	return 0;
}

 希望能帮助到各位同志，祝天天开心，学业进步！