蓝桥杯 - 穿越雷区
解题思路：
dfs
方法一：
import java.util.Scanner;public class Main {static char[][] a;static int[][] visited;static int[] dx = { 0, 1, 0, -1 };static int[] dy = { 1, 0, -1, 0 };static long min = Long.MAX_VALUE;static long count = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();a = new char[n][n];visited = new int[n][n];int startx = 0;int starty = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = in.next().charAt(0);if (a[i][j] == 'A') {startx = i;starty = j;}}}dfs(startx, starty, n);if(min == Integer.MAX_VALUE) min = -1;System.out.println(min);}public static void dfs(int x, int y, int n) {visited[x][y] = 1;if (a[x][y] == 'B') {min = Math.min(min, count);return;}for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] != a[x][y] && visited[xx][yy] == 0) {count++;dfs(xx, yy, n);visited[xx][yy] = 0;count--;}}}}方法二：
时间复杂度更低，不易超时
import java.util.Scanner;public class Main {static char[][] a;static int[][] visited;static int[] dx = { 0, 1, 0, -1 };static int[] dy = { 1, 0, -1, 0 };static int min = Integer.MAX_VALUE;static int n;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();a = new char[n][n];visited = new int[n][n];String str[] = new String[n];int startx = 0;int starty = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = in.next().charAt(0);visited[i][j] = Integer.MAX_VALUE;if (a[i][j] == 'A') {startx = i;starty = j;}}}dfs(startx, starty, 0);if (min == Integer.MAX_VALUE)min = -1;System.out.println(min);}public static void dfs(int x, int y, int step) {visited[x][y] = step;if (a[x][y] == 'B') {min = Math.min(min, step);return;}for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] != a[x][y] && visited[x][y] + 1 < visited[xx][yy]) {dfs(xx, yy, step + 1);}}}
}