题目描述

如题:发现书上有更好的题解,思路还是太复杂了,但是写都写了就留在这吧= = 有兴趣的话可以看看。

样例

这个样例对应的输出是2



1
11101
11101
11110
11111
11111

这个样例对应的输出是2

算法1

(经过一些优化的dfs,结果超时)

一开始的思路是,既然这个是5X5,那么我应该可以直接dfs吧（？？？没看清题目的我）
但我还是做了一些减少计算量的操作（几乎没起到什么作用）
在我的仔细分析之下,我发现:
/*
* 每次只需要改变0或者身边(上下左右)有0的1
* 因为如若附近都没有0,那么只能让这次修改的
* 浪费一次修补回来的机会。
* 所以在这里我只改上下左右或中间有0的节点…
/
于是我就着这个思路写了一个巨长又臭的代码,不想看的直接跳过吧。。。

public class acwing95 {
    /**
     * 每次只需要改变0或者身边(上下左右)有0的1
     * 因为如若附近都没有0,那么只能让这次修改的
     * 浪费一次修补回来的机会。
     * 所以在这里我只改上下左右或中间有0的节点...
     */
    static int[][] matrix;
    static boolean[][] has;
    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        scanner.nextLine();
        matrix = new int[5][5];
        for (int i = 0; i < m; i++) {
            has = new boolean[5][5];
            for (int j = 0; j < 5; j++) {
                char[] ch = scanner.nextLine().toCharArray();
                for (int k = 0; k < 5; k++) {
                    matrix[j][k] = ch[k] - '0';
                }
            }
            if (scanner.hasNextLine()) {
                scanner.nextLine();
            }
            int res = dfs (1);
            System.out.println(res);
        }
    }

    public static int dfs (int times) {
        if (isRight()) {
            return times - 1;
        }
        if (times == 7) {
            return -1;
        }
        int res = -1;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (isValid(i, j)) {
                    change(i, j);
                    has[i][j] = true;
                    int r = dfs (times + 1);
                    change(i, j);
                    has[i][j] = false;
                    if (r != -1 && (res == -1 || res > r)) {
                        res = r;
                    }
                }
            }
        }
        return res;
    }
    //判断目前矩阵是否全为1
    public static boolean isRight () {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (matrix[i][j] != 1) {
                    return false;
                }
            }
        }return true;
    }
    //判断当前输入的坐标是不是有效坐标（这个操作好像并没有减低我的计算量,可能因为矩阵太小了。。。）
    public static boolean isValid (int i, int j) {
        return !has[i][j] && (matrix[i][j] == 0 || (i + 1 < 5 && matrix[i + 1][j] == 0) || (j + 1 < 5 && matrix[i][j + 1] == 0)
                || (i > 0 && matrix[i - 1][j] == 0) || (j > 0 && matrix[i][j - 1] == 0));
    }
    //输入一个坐标,将它和它上下左右改变一下位置
    public static void change (int i, int j) {
        matrix[i][j] = matrix[i][j] != 0 ? 0 : 1;
        if (i > 0) {
            matrix[i - 1][j] = matrix[i - 1][j] != 0 ? 0 : 1;
        }
        if (j > 0) {
            matrix[i][j - 1] = matrix[i][j - 1] != 0 ? 0 : 1;
        }
        if (i + 1 < 5) {
            matrix[i + 1][j] = matrix[i + 1][j] != 0 ? 0 : 1;
        }
        if (j + 1 < 5) {
            matrix[i][j + 1] = matrix[i][j + 1] != 0 ? 0 : 1;
        }return;
    }
}

算法2

(这次是AC的算法了:广度优先搜索+状态压缩+dp) $O(1)$ : 25^6 hhh

吸取了上一次的教训,我首先想到的是,我一定要用dp来写这道题目,
因为只要我用了dp,那么无论输入的n为多少,我都不用管因为我能直
接找到当前的状态直接得出结果！
这里用二进制数表示矩阵的状态(如若对这个不是很理解可以先看看哔哩哔哩y神昨晚录播的第三道题),
恰好这个矩阵只有25个节点且每个节点
只有0或1两种状态。
这时候我想到了我写过的另一道题目,这道题也是这种类型的(一个拼图游戏的问题)。。。
这种类型的题目可以利用广度优先搜索,从成功的状态,来逆推所有能成功到达的状态
恰巧这个只能推六次,所以我就弄了个界定层次的一个end（整型）,来判断当前处于第几层
因为广度优先搜索具有寻找最短路径的那个特点,在这里正好用得上。也就是说,这个节点只要载入
就一定会是最小的次数。
到这里就基本上没什么问题了,我就直接贴代码了。代码上会对函数功能进行注解
时间复杂度分析：25^6

Java 代码

import java.util.*;

/**
 * acwing 95 费解的开关
 * 2019年1月15日21:20:17
 * @author HP
 *
 */

public class Main {
    /**
     * 首先可以明确的是,一个状态如若最少点击三个不同的点能全部为1
     * 那么,与点击这三个点的顺序是无关的。
     * 这里采用状态压缩,将矩阵用一个整型表示。
     * 然后利用广度优先搜索,全是1的状态下往回点
     * dp内元素先默认为-1,然后如若在六次之内能到达
     * 的元素都会进入队列中,并且赋都会最小次数的值（bfs找单源最短路径也是利用了这个性质）
     * 如若dp数组中已经有所有结果了,那么之后的无论是多少组数据都可以直接通过了。
     */
    static int[] dp;
    static int n = 1 << 25;
    static boolean[] has;
    public static void main (String[] args){
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        scanner.nextLine();
        dp = new int[n];
        has = new boolean[n];
        Arrays.fill(dp, -1);
        dp[n - 1] = 0;
        has[n - 1] = true;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(n - 1);
        int times = 0;
        int end = n - 1;
        while (!queue.isEmpty() && times < 7) {
            int val = queue.poll();
            dp[val] = times;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    int num = change(val, i, j);
                    if (!has[num]) {
                        queue.add(num);
                        has[num] = true;
                    }
                }
            }
            if (end == val) {
                times++;
                end = queue.getLast();
            }
        }
        for (int i = 0; i < m; i++) {
            int matrix = 0;
            for (int j = 0; j < 5; j++) {
                char[] ch = scanner.nextLine().toCharArray();
                for (int k = 0; k < 5; k++) {
                    matrix += ((ch[k] - '0') << (j * 5 + k));
                }
            }
            if (scanner.hasNextLine()) {
                scanner.nextLine();
            }
            System.out.println(dp[matrix]);
        }
    }

    /**
     * 给出一个代表5X5矩阵的数
     * 按照费解的开关定义的那样
     * 去操作后会生成另一个代表
     * 5X5矩阵的数,并返回。
     * @param val
     * @param i
     * @param j
     * @return
     */
    public static int change (int val, int i, int j) {
        //(val >> i * 5 + j) & 1 : 代表的是当前的i,j坐标对应位置的位
        //如若这个位置是1,则减去1为0,如若这个位置是0,则减去-1为1;
        val -= (1 & (val >> i * 5 + j)) != 0 ? 1 << i * 5 + j : -(1 << i * 5 + j);
        if (i > 0) {
            val -= (1 & (val >> (i - 1) * 5 + j)) != 0 ? 1 << (i - 1) * 5 + j : -(1 << (i - 1) * 5 + j);
        }
        if (j > 0) {
            val -= (1 & (val >> i * 5 + j - 1)) != 0 ? 1 << i * 5 + j - 1 : -(1 << i * 5 + j - 1);
        }
        if (i < 4) {
            val -= (1 & (val >> (i + 1) * 5 + j)) != 0 ? 1 << (i + 1) * 5 + j : -(1 << (i + 1) * 5 + j);
        }
        if (j < 4) {
            val -= (1 & (val >> i * 5 + j + 1)) != 0 ? 1 << i * 5 + j + 1 : -(1 << i * 5 + j + 1);
        }return val;
    }
}