3035: LETTERS最多能走过的不同字母的个数

解题思路:

注意事项:dfs函数中要注意最后一定要写ch_flag[ch_idx]=false;防止回溯的时候出现错误
参考代码:

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

int R,S;

char ch[21][21];

bool ch_flag[27];

int max_count=0;

int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void dfs (int r,int c,int count){

    if(count>max_count){

        max_count=count;

    }

    for(int i=0;i<4;i++){

        int n_r=r+dirs[i][0];

        int n_c=c+dirs[i][1];

        if(n_r>=0 && n_r<R && n_c>=0 && n_c<S){

            int ch_idx=ch[n_r][n_c]-'A';

            if(!ch_flag[ch_idx]){

                ch_flag[ch_idx]=true;

                dfs(n_r,n_c,count+1);

                ch_flag[ch_idx]=false;

            }

        }

    }

}

int main()

{

scanf("%d%d",&R,&S);

for(int i=0;i<R;i++){

    scanf("%s",&ch[i]);

}

for (int i=0;i<R;i++){

    ch_flag[i]=false;

}

int start_ch=ch[0][0]-'A';

ch_flag[start_ch]=true;

dfs(0,0,1);

printf("%d",max_count);

return 0;

}