蓝桥杯 - 穿越雷区

解题思路：

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];
        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);
                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);
            }
        }
    }
}