走迷宫、八数码
走迷宫
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。
数据范围
1≤n,m≤100
输入样例：
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0输出样例：
8dfs超时
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N = 110; static boolean f[][]=new boolean[N][N]; static int a[][]=new int[N][N],res=Integer.MAX_VALUE; static int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[] = br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); for (int i = 0; i < n; i++) { g = br.readLine().split(" "); for (int j = 0; j < m; j++) { a[i][j]=Integer.parseInt(g[j]); } } f[1][1]=true; dfs(0,0,n,m,0); System.out.println(res); } static void dfs(int x,int y,int n,int m,int step){ if(x==n-1 && y==m-1){ res=Math.min(res, step); return; } for (int i = 0; i < 4; i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx<0||nx>n||ny<0||ny>m)continue; if(a[nx][ny]==1)continue; if(f[nx][ny]==true)continue; f[nx][ny]=true; dfs(nx, ny, n, m, step+1); f[nx][ny]=false; } } }import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; public class Main { static int N = 110; static boolean f[][]=new boolean[N][N]; static int a[][]=new int[N][N]; static int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[] = br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); for (int i = 0; i < n; i++) { g = br.readLine().split(" "); for (int j = 0; j < m; j++) { a[i][j]=Integer.parseInt(g[j]); } } Queue<int[]> queue=new LinkedList<int[]>(); int t[]={0,0,0}; queue.add(t);f[0][0]=true; int res=0; while(!queue.isEmpty()){ int p[]=queue.poll(); if(p[0]==n-1 && p[1]==m-1){ System.out.println(p[2]); break; } for (int i = 0; i < 4; i++) { int nx=p[0]+dx[i],ny=p[1]+dy[i]; if(nx<0 || nx>=n || ny<0 || ny>=m)continue; if(f[nx][ny]==true || a[nx][ny]==1)continue; int son[]={nx,ny,p[2]+1}; queue.add(son);f[nx][ny] = true; } } } }八数码
在一个 3×3 的网格中，1∼8 这 8 个数字和一个x恰好不重不漏地分布在这 3×3 的网格中。
例如：
1 2 3 x 4 6 7 5 8在游戏过程中，可以把x与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3 4 5 6 7 8 x例如，示例中图形就可以通过让x先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3 x 4 6 4 x 6 4 5 6 4 5 6 7 5 8 7 5 8 7 x 8 7 8 x现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将 3×3 的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3 x 4 6 7 5 8则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出 −1。
输入样例：
2 3 4 1 5 x 7 6 8输出样例
19import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; public class Main { static int N = 110; static boolean f[][]=new boolean[N][N]; static int a[][]=new int[N][N]; static int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g = String.join("", br.readLine().split(" ")); char c[]=g.toCharArray(); Set<String> set=new HashSet<>(); Queue<Node> queue=new LinkedList<>(); queue.add(new Node(c,0));set.add(g); while(!queue.isEmpty()){ Node node=queue.poll(); char p[]=node.p; int step=node.step; if("12345678x".equals(new String(p))){ System.out.println(step); return; } int idx=new String(p).indexOf('x'); //System.out.println(idx); int x=idx/3,y=idx%3; for (int i = 0; i < 4; i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx<0 || nx>= 3 || ny<0 ||ny>=3)continue; int exa=nx*3+ny; char pp[]=Arrays.copyOfRange(p,0,9); char t=pp[idx]; pp[idx]=pp[exa]; pp[exa]=t; if(set.contains(new String(pp)))continue; queue.add(new Node(pp,step+1));set.add(new String(pp)); } } System.out.println(-1); } static class Node{ char p[]; int step; public Node() { // TODO Auto-generated constructor stub } public Node(char p[], int step) { this.p = p; this.step = step; } } }