【題目描述】
給出一個row×colrow×col的大寫字母矩陣，一開始的位置為左上角，你可以向上下左右四個方向移動，并且不能移向曾經經過的字母。問最多可以經過幾個字母。
【輸入】
第一行，輸入字母矩陣行數RR和列數SS，1≤R,S≤201≤R,S≤20。
接著輸出RR行SS列字母矩陣。
【輸出】
最多能走過的不同字母的個數。
【輸入樣例】
3 6
HFDFFB
AJHGDH
DGAGEH
【輸出樣例】
6
原題鏈接：信息學奧賽一本通（C++版）在線評測系統
學習鏈接：《信息學奧賽一本通》搜索與回溯算法：1212LETTERS_嗶哩嗶哩_bilibili
【解題思路】
- 輸入字母矩陣
- 從左上角作為第一步，開始對其上下左右四個方向開始搜索，若四個方向都已無法搜素或搜索完畢，則回溯?
- 直到所有路徑全部搜索完畢，找到最長的路徑（不能出現相同字母）
代碼如下：
#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;
}?希望能幫助到各位同志，祝天天開心，學業進步！
