c++信息学奥赛一本通1212题解-创新互联

1212：LETTERS

时间限制: 1000 ms 内存限制: 65536 KB

创新互联公司专注于企业营销型网站、网站重做改版、冷水江网站定制设计、自适应品牌网站建设、HTML5建站、成都做商城网站、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为冷水江等各大城市提供网站开发制作服务。

提交数: 31679 通过数: 14329

【题目描述】

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

【输入】

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

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

【输出】

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

【输入样例】

3 6

HFDFFB

AJHGDH

DGAGEH

【输出样例】

6

题解

较为棘手的深搜题，坑很多，麻烦也很多。

第一个麻烦，输入是字符，中间转换成数字时不要弄错。

第二个麻烦，很难找到什么时候统计新增加的访问个数好，后来那我们索性就麻烦一点，把它写入形参，每次运行时与全局变量比较。注意，这样写是没有问题的，因为在最后一次执行时不会继续搜索，故该答案就是正确的答案。

同时也需要注意一个问题，出发前需要把起点先标记掉，不然就容易出错。

除此之外，就很简单啦，上代码！

#includeusing namespace std;
const int M=25;
char e[M][M];
int ans;
int r,s; 
int vis[30],dx[]={1,-1,0,0},dy[]={0,0,1,-1};
void dfs(int x,int y,int ans1){
    

    ans=max(ans,ans1);
    int d=0;
    for(int i=0; i<4; i++){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>=1 && tx<=r && ty>=1 && ty<=s && !vis[e[tx][ty]-'A'+1]){
        
        vis[e[tx][ty]-'A'+1]=1;
        dfs(tx,ty,ans1+1);
        vis[e[tx][ty]-'A'+1]=0;
    }
    }
}
int main(){
    scanf("%d%d",&r,&s);
    for(int i=1; i<=r; i++)
        scanf("%s",e[i]+1);
    vis[e[1][1]-'A'+1]=1;
    dfs(1,1,1);
    printf("%d",ans);
    return 0;
}

码字不易，关注点赞收藏支持一下吧！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站标题：c++信息学奥赛一本通1212题解-创新互联
分享URL：http://jkwzsj.com/article/docdee.html