信息学奥赛一本通T1212：搜索与回溯算法（DFS） LETTERS

【题目描述】给出一个roe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。【输入】第一行，输入字母矩阵行数R和列数S，1≤R,S≤20。接着输出R行S列字母矩阵。【输出】最多能走过的不同字母的个数。【输入样例】3 6【输出样例】6【源程序】

信息学奥赛一本通T1212：LETTERS

【题目描述】

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

【输入】

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

接着输出R行S列字母矩阵。

【输出】

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

【输入样例】

3 6
HFDFFB
AJHGDH
DGAGEH

【输出样例】

6

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 30
using namespace std;
int r,s;
char a[N][N];
int vis[N][N];
int num[26];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int maxx=0;
void dfs(int x,int y,int step)
{
    if(maxx<step)
        maxx=step;
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>=0&&nx<r&&ny>=0&&ny<s&&vis[nx][ny]==0&&num[a[nx][ny]-'A']==0)
        {
            vis[nx][ny]=1;
            num[a[nx][ny]-'A']=1;
            dfs(nx,ny,step+1);
            vis[nx][ny]=0;
            num[a[nx][ny]-'A']=0;
        }
    }
}
int main()
{
    cin>>r>>s;
    for(int i=0;i<r;i++)
        for(int j=0;j<s;j++)
            cin>>a[i][j];
    num[a[0][0]-'A']=1;
    vis[0][0]=1;
    dfs(0,0,1);
    cout<<maxx<<endl;
    return 0;
}

信息学奥赛一本通T1212：搜索与回溯算法（DFS） LETTERS 归属于搜索与回溯算法（DFS），更多同类题解源程序见：搜索与回溯算法（DFS）和 LETTERS

发表于 2020-04-28 10:20
阅读 ( 1243 )
分类：信息学奥赛一本通

信息学奥赛一本通T1212：搜索与回溯算法（DFS） LETTERS

信息学奥赛一本通T1212：LETTERS

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【源程序】

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »