1212：LETTERS

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 18193 ??? 通過數: 8212

【題目描述】

給出一個roe×col的大寫字母矩陣，一開始的位置為左上角，你可以向上下左右四個方向移動，并且不能移向曾經經過的字母。問最多可以經過幾個字母。

【輸入】

第一行，輸入字母矩陣行數R和列數S，1≤R,S≤20。

接著輸出R行S列字母矩陣。

【輸出】

最多能走過的不同字母的個數。

【輸入樣例】

3 6 HFDFFB AJHGDH DGAGEH

【輸出樣例】

6

【分析】

? ? ? ? 這是一道簡單的搜索題，題目的意思是指在字母表中，向上下左右四個方向探索，如果字母重復則結束這個方向的探索。以樣例為例，先從H開始探索，向上不能探索，向右繼續探索，H->F，向上不能探索，向右H->F->D，再向右則F重復，向下H重復，向左F重復，所以，回溯到F，繼續向下探索，H->F->J，...，在探索的過程中找到最大值（走過的不同字母的個數）。

【參考代碼】

#include<stdio.h> #include<string.h> #define MAXN 25int row,col; char map[MAXN][MAXN]; //字母矩陣 int u[4]={1,0,-1,0}; //方向數組 int v[4]={0,-1,0,1}; //方向數組 int visted[26]; //標記字母，0沒訪問過，1訪問過 int vistedmap[MAXN][MAXN]; //標記字母矩陣，0沒訪問，1訪問過 int max;void dfs(int x,int y,int step) {int i,nx,ny;if(step>max)max=step;for(i=0;i<4;i++){nx=x+u[i];ny=y+v[i];if(nx>=0 && nx<row && ny>=0 && ny<col && !visted[map[nx][ny]-'A'] && !vistedmap[nx][ny]){visted[map[nx][ny]-'A']=1;vistedmap[nx][ny]=1;dfs(nx,ny,step+1);visted[map[nx][ny]-'A']=0;vistedmap[nx][ny]=0;}} } int main() {int i,j; scanf("%d%d",&row,&col);for(i=0;i<row;i++){scanf("%s",&map[i]);getchar();}//從第一個點出發，向四周做選擇visted[map[0][0]-'A']=1;vistedmap[0][0]=1; dfs(0,0,1); //因為第一個點有一個字母，故已訪問一個字母，所以第三個參數為1printf("%d\n",max);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1212

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1212：LETTERS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。