当前位置：首页 > ai >正文

【数据结构入门训练DAY-32】LETTERS

ai 2025/5/15 2:06:03

本文介绍了一个关于使用深度优先搜索（DFS）解决字母矩阵问题的训练内容。题目要求在一个R×S的大写字母矩阵中，从左上角开始移动，可以上下左右四个方向移动，但不能重复经过相同的字母，目标是找出最多能经过的不同字母数量。解题思路是通过DFS递归搜索矩阵中的每个字母，使用布尔数组标记已访问的字母，并在每个位置检查上下左右的字母是否未被访问过，继续递归搜索。文章还强调了在编码过程中if和else if语句的正确使用，以及严谨编码习惯的重要性。通过这次训练，不仅提升了解题思维，还加深了对编程细节的理解。

文章目录

前言
一、题目
二、解题思路
总结

前言

本次训练内容

训练DFS处理相同字母的问题。
对编码习惯的养成。
训练解题思维。

一、题目

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

输入格式

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

输出格式

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

样例输入

3 6
HFDFFB
AJHGDH
DGAGEH

样例输出

二、解题思路

今天的题目，我的思路就是依次搜索回溯矩阵里的各个字母，如果遇到了新的字母就对其进行标记。我是使用bool来进行标记的，然后建立一个二维数组进行存储字母矩阵，再根据题意依次对当前字母位置的上下左右进行判断；具体代码实现如下：

#include <bits/stdc++.h>
using namespace std;
int R,S;
int sum=0;
char Array[26][26];
bool Check[10000];//标记处
void DFS(int x,int y,int k) {//定义的DFS函数
//处理逻辑if (x-1>0&&!Check[Array[x-1][y]]) {//上Check[Array[x-1][y]] = true;DFS(x-1,y,k+1);Check[Array[x-1][y]] = false;}if (y-1>0&&!Check[Array[x][y-1]]) {//左Check[Array[x][y-1]] = true;DFS(x,y-1,k+1);Check[Array[x][y-1]] = false;}if (x+1<=R&&!Check[Array[x+1][y]]) {//下Check[Array[x+1][y]] = true;DFS(x+1,y,k+1);Check[Array[x+1][y]] = false;}if (y+1<=S&&!Check[Array[x][y+1]]) {//右Check[Array[x][y+1]] = true;DFS(x,y+1,k+1);Check[Array[x][y+1]] = false;}sum=max(sum,k);//取最多的情况
}
int main() {cin>>R>>S;for (int i=1;i<=R;++i) {for (int j=1;j<=S;++j) {cin>>Array[i][j];}}Check[Array[1][1]] = true;//标记矩阵第一个字母DFS(1,1,1);cout<<sum;
}

注意if和else if的使用区别！！！