【题目描述】
给出一个R行S列的大写字母矩阵,一开始的位置为左上角,你可以向上下左右四个方向移动,并且不能移向曾经经过的字母。问最多可以经过几个字母。
【输入】
第一行,输入字母矩阵行数R和列数S,1≤R,S≤20。
接着输出R行S列字母矩阵。
【输出】
最多能走过的不同字母的个数。
【输入样例】
3 6
HFDFFB
AJHGDH
DGAGEH
【输出样例】
6
【题目描述】
给出一个R行S列的大写字母矩阵,一开始的位置为左上角,你可以向上下左右四个方向移动,并且不能移向曾经经过的字母。问最多可以经过几个字母。
【输入】
第一行,输入字母矩阵行数R和列数S,1≤R,S≤20。
接着输出R行S列字母矩阵。
【输出】
最多能走过的不同字母的个数。
【输入样例】
3 6
HFDFFB
AJHGDH
DGAGEH
【输出样例】
6
以下回复参考:皆我百晓生、券券喵儿等免费微信小程序作答:
解析: 这是一个深度优先搜索(DFS)的问题,从左上角开始,向四个方向进行搜索,每次搜索到一个新的字母,就将计数器加1,然后将该字母标记为已访问。为了避免重复访问,需要一个二维布尔数组来记录每个位置是否被访问过。
代码如下:
#include <iostream>
#include <vector>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool isValid(int x, int y, int R, int S, vector<vector<bool>>& visited) {
return x >= 0 && x < R && y >= 0 && y < S && !visited[x][y];
}
int dfs(int x, int y, vector<vector<char>>& matrix, vector<vector<bool>>& visited) {
if (!isValid(x, y, matrix.size(), matrix[0].size(), visited)) {
return 0;
}
visited[x][y] = true;
int count = 1;
for (int i = 0; i < 4; i++) {
count += dfs(x + dx[i], y + dy[i], matrix, visited);
}
return count;
}
int main() {
int R, S;
cin >> R >> S;
vector<vector<char>> matrix(R, vector<char>(S));
vector<vector<bool>> visited(R, vector<bool>(S, false));
for (int i = 0; i < R; i++) {
for (int j = 0; j < S; j++) {
cin >> matrix[i][j];
}
}
cout << dfs(0, 0, matrix, visited) << endl;
return 0;
}
这段代码首先定义了四个方向的移动,然后定义了一个isValid函数来判断当前位置是否可以访问。然后在dfs函数中,首先判断当前位置是否可以访问,如果可以,就将其标记为已访问,并将计数器加1,然后向四个方向进行搜索。最后在main函数中,首先读取输入的矩阵,然后调用dfs函数进行搜索,并输出结果。