算法分析
爆搜
-
1、用
set
或者map
对字母进行判重 -
2、假设当前位置是
(x,y)
,往4
个方向的点进行深度优先遍历,任意4个方向的点(a,b)
未在set
或者map
中出现过,则递归到下一层
Java 代码
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main{
static int N = 25;
static int n,m;
static char[][] g = new char[N][N];
static Set<Character> set = new HashSet<Character>(); //对字母进行判重
static int[] dx = new int[] {-1,0,1,0};
static int[] dy = new int[] {0,1,0,-1};
static int ans = 0;
static void dfs(int x,int y,int nums)
{
ans = Math.max(ans, nums);
for(int i = 0;i < 4;i ++)
{
int a = x + dx[i];
int b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(!set.contains(g[a][b]))
{
set.add(g[a][b]);
dfs(a,b,nums + 1);
set.remove(g[a][b]);//恢复现场
}
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0;i < n;i ++)
{
char[] temp = scan.next().toCharArray();
for(int j = 0;j < m;j ++)
g[i][j] = temp[j];
}
set.add(g[0][0]);
dfs(0,0,1);
System.out.println(ans);
}
}