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

LETTERS(dfs)

article 2025/3/13 5:04:44

题目描述

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

输入格式

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

输出格式

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

样例输入

复制

3 6
HFDFFB
AJHGDH
DGAGEH

样例输出

复制

提示

零基础同学可以先学习视频课程，包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程，提供视频讲解以及配套习题，还有老师答疑，点击这里了解课程详情

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=21;
char a[N][N];
bool visited[N][N];
int count1=0;
int maxn=INT_MIN;
int next1[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
set<char>used;
void dfs(int x,int y,int count1)
{
   maxn=max(count1,maxn);
   for(int i=0;i<4;i++)
   {
       int tx=x+next1[i][0];
       int ty=y+next1[i][1];
       if(tx>=0&&ty>=0&&tx<=n-1&&ty<=m-1&&used.find(a[tx][ty]) == used.end())
       {
           if(visited[tx][ty]==false)
           {
               used.insert(a[tx][ty]);
               dfs(tx,ty,count1+1);
               used.erase(a[tx][ty]);

           }
       }
   }
}
int main ()
{
   cin>>n>>m;
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<m;j++)
       {
           cin>>a[i][j];
       }
   }
   used.insert(a[0][0]);
   dfs(0,0,1);
   cout<<maxn<<endl;
   return 0;
}