题目

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

代码

#include <iostream>
using namespace std;
int row,col;
char vis[1001][1001];
char visted[1001];
int mv[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int max1=1;
bool pd(int k,int xx,int yy){
    for(int i=0;i<k;i++){
        if(visted[i]==vis[xx][yy]) return false;
    }
    return true;
}
void search(int k,int x,int y){
    for(int i=0;i<4;i++){
        int xx=x+mv[i][0];
        int yy=y+mv[i][1];
        if(xx>=0 && xx<row && yy>=0 && yy<col && pd(k,xx,yy)){
            visted[k]=vis[xx][yy];
            if(k>max1) max1=k;
            search(k+1,xx,yy);
            
        }
    }
}
int main(){
    cin>>row>>col;
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            cin>>vis[i][j];
    visted[0]=vis[0][0];
    search(2,0,0);
    cout<<max1<<endl;
}

简析

• 二维数组套模版题
• 可参考文章系列一、系列四
• 就是定义一个移动方式，然后移动一下，判断一下。可以移动的话就移动，然后search这个新的点。

A for循环范围

4种移动方式，for循环范围1～4

B 判断可选

• 没有越界，如（0，0）这个点移动（-1，0）的话就超出矩阵范围了
• 定义一个数组，存储访问过的数，判断这个新的点是否在访问过的点的数组中

if(xx>=0 && xx<row && yy>=0 && yy<col && pd(k,xx,yy)){

bool pd(int k,int xx,int yy){
    for(int i=0;i<k;i++){
        if(visted[i]==vis[xx][yy]) return false;
    }
    return true;
}

选中

• 放入存储过的数的数组中
• 判断k是否大于max1了，大于了，这个K就是最大
• 搜索下一层

        if(xx>=0 && xx<row && yy>=0 && yy<col && pd(k,xx,yy)){
            visted[k]=vis[xx][yy];
            if(k>max1) max1=k;
            search(k+1,xx,yy);
        }