一本通 1212：LETTERS

题目描述

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

---

输入

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

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

---

输出

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

---

输入样例

3 6

HFDFFB

AJHGDH

DGAGEH

---

输出样例

6

---

思路

一道简单的搜索回溯题目

我们可以定义几个数组，和最大值maxn，输入之后进行搜索，一次一次搜，如果当前进行的步骤比maxn大，就把step（当前步骤）的值赋给maxn，最后输出maxn即可

---

代码

#include<bits/stdc++.h>

using namespace std;

char a[28][28];

int vis[28][28];

int num[27];

bool b[27];

int f[5][3]= {{0,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}};

int r,s;

int maxn=0;

void dfs(int x,int y,int st){

	if(maxn<st){

		maxn=st;

	}

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

		int nx=x+f[i][1];

		int ny=y+f[i][2];

		if(nx>0&&nx<=r&&ny>0&&ny<=s&&vis[nx][ny]==0&&num[a[nx][ny]-64]==0){

			vis[nx][ny]=1;

			num[a[nx][ny]-64]=1;

			dfs(nx,ny,st+1);

			vis[nx][ny]=0;

			num[a[nx][ny]-64]=0;

		}

	}

}

int main() {

	scanf("%d%d",&r,&s);

	for(int i=1; i<=r; i++) {

		for(int j=1; j<=s; j++) {

			cin>>a[i][j];

		}

	}

	num[a[1][1]-64]=1;

	vis[1][1]=1;

	dfs(1,1,1);

	cout<<maxn<<'\n';

	return 0;

}