LEETERS题解

【题目描述】

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

【输入】

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

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

【输出】

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

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

6

#include <iostream>
#include <vector>using namespace std;const int MAXN = 20;
char matrix[MAXN][MAXN];
bool visited[26];
int row , col;
int maxCount = 0;int dx[] = {-1 , 1  , 0 , 0};
int dy[] = {0 , 0 , - 1, 1};// 深度优先搜索函数
void dfs(int x  , int y , int count) {//跟新最大经过字母数maxCount = max (maxCount , count);//遍历四个选项for(int i = 0; i < 4 ; ++i ){int newX = x + dx[i];int newY = y + dy[i];//check 位置是否合法if(newX >= 0  && newX < row && newY >= 0 && newY < col){int letterindex = matrix[newX][newY] - 'A';if(!visited[letterindex]) {visited[letterindex] = true;dfs(newX , newY   , count+1) ;visited[letterindex] = false; //回溯}}}}
int main() {cin >> row >> col;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {cin >> matrix[i][j];}}// 标记起点字母已访问int startLetterIndex = matrix[0][0] - 'A';visited[startLetterIndex] = true;// 从左上角开始深度优先搜索dfs(0, 0, 1);cout << maxCount << endl;return 0;
}