搜索练习题LETTERS

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1212 或者http://poj.org/problem?id=1154

题目描述：

给出一个 $r o e \times c o l$

【输入】

第一行，输入字母矩阵行数 $R$

接着输出 $R$

【输出】

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

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN=50;
 4 int r,s,ans;                                    // R,S分别表示行数和列数，ans表示最多经过字母数
 5 char a[MAXN][MAXN]; 
 6 int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };   // dir数组用于表示上下左右4个方向
 7 bool vis[26];   // vis数组用于记录26个字母是否有走过，其中'A'对应vis[0],'B'对应vis[1]，…
 8 //用于判断第x行第y列的元素是否超过地图边界
 9 bool isp(int x,int y){
10     return x>=0&&x<r&&y>=0&&y<s;                //一开始写了x<=r&&y<=s不对 ，后来发现数组越界了 
11 }
12 void dfs(int x,int y,int sum){                    // dfs函数用于搜索，它表示当前在第x行第y列，已经走了sum步
13     vis[a[x][y]-'A']=true;                        // 首先将当且(x,y)这个点对应的字母的vis值标记为true
14     if(sum>ans)    ans=sum;
15     for(int i=0;i<4;i++){
16         int nx=x+dir[i][0];
17         int ny=y+dir[i][1];
18         if(isp(nx,ny) && !vis[a[nx][ny]-'A'])
19             dfs(nx,ny,sum+1);
20     }
21     vis[a[x][y] - 'A' ] = false;                  // 因为搜索是尝试放，所以推出本次搜索记得将vis值标记回false    
22 }
23 int main(){
24     cin>>r>>s;
25     for(int i=0;i<r;i++)
26         for(int j=0;j<s;j++)
27             cin>>a[i][j];
28     dfs(0,0,1);
29     cout<<ans<<endl;
30     return 0;
31 }