T1212：LETTERS

【题目描述】

给出一个R * S的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。 $r o e \times c o l$

【输入】

第一行，输入字母矩阵行数R和列数S， 1 <= R, S <= 20

接着输入R行S列的字母矩阵

【输出】

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

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

代码如下

 1 #include<iostream>
 2 using namespace std;
 3 char s[30][30];
 4 int row, col, maxn = -1;
 5 int vis[30][30], book[1010];
 6 int pos[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
 7 void dfs(int x, int y, int step){
 8     if(step > maxn)    maxn = step;
 9     for(int i = 0; i < 4; i++){
10         int tx = pos[i][0] + x, ty = pos[i][1] + y;
11         if(tx < 0 || tx > row - 1 || ty < 0 || ty > col - 1)    continue;
12         if(!vis[tx][ty] && !book[s[tx][ty]]){
13             vis[tx][ty] = 1;
14             book[s[tx][ty]] = 1;
15             dfs(tx, ty, step + 1);
16             book[s[tx][ty]] = 0;
17             vis[tx][ty] = 0;
18         }  
19     }
20 }
21 int main(){
22     cin >> row >> col;
23     for(int i = 0; i < row; i++){
24         for(int j = 0; j < col; j++){
25             cin >> s[i][j];
26         }
27     } 
28     vis[0][0] = 1;
29     book[s[0][0]] = 1;
30     dfs(0, 0, 1);
31     cout << maxn << endl;
32     return 0;
33 }

LETTERS

注意点

初始化
边界处理