各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

费解的开关

February 19, 2019 • Read: 428 • 算法

这题做法很简单,首先考虑什么情况下需要摁开关,因为每次摁开关都会导致十字区域的开关状态变,因此,当第i行第j列的开关是关的情况下,才需要摁第i+1行第j列的开关

假如第一行固定的情况下,例如第一行是11011,那么第二行的第3列就必须摁一下,此时第一行变成了11111。因为第二行中某一个摁了一下,导致第二行发生变化,例如变成01011,那么第三行就需要摁第1列和第3列的开关,此时第二行也变成了11111,一直下去

上面说的是第一行固定的情况,但是第一行也是可以摁的,并且摁的方法数有$2^5$种,所以需要先对第一行开关摁的情况进行一个枚举,然后再递推后面所有行的情况

这里要注意的是,由于最后一行没有下一行,所以最后一行的状态是无法改变的,当我们从上往下摁到最后一行的时候,需要判断最后一行是否是全1的状态,如果是,就更新摁的次数(每次取最小值)

import java.util.Scanner;

public class Main {
    static int[][] map = new int[5][5];
    static int[][] move = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while ((T--) != 0) {
            for (int i = 0; i < 5; i++) {
                String tmp = cin.next();
                for(int j = 0; j < 5; j++)
                    map[i][j] = tmp.charAt(j) - '0';
            }
            System.out.println(dfs());
        }
    }
    
    static int dfs() {
        int ans = Integer.MAX_VALUE >> 1;
        for (int i = 0; i < (1 << 5); i++) {
            int sum = 0;
            int[][] copy = new int[5][5];
            for (int row = 0; row < 5; row++)
                for (int col = 0; col < 5; col++)
                    copy[row][col] = map[row][col];
            for (int j = 0; j < 5; j++)
                if ((i >> j & 1) == 1) {
                    sum++;
                    change(0, j);
                }
            
            for (int k = 0; k < 4; k++) // 最后一行不摁
                for (int col = 0; col < 5; col++)
                    if (map[k][col] == 0) {
                        sum++;
                        change(k + 1, col);
                    }
            boolean flag = true;
            for (int col = 0; col < 5; col++)
                if (map[4][col] == 0) {
                    flag = false;
                    break;
                }
            if (flag)
                ans = Math.min(ans, sum);
            for (int row = 0; row < 5; row++)
                for (int col = 0; col < 5; col++)
                    map[row][col] = copy[row][col];
        }
        return ans <= 6 ? ans : -1;
    }
    
    static void change(int x, int y) {
        for (int i = 0; i < 5; i++) {
            int nx = x + move[i][0];
            int ny = y + move[i][1];
            if (nx < 5 && nx >= 0 && ny < 5 && ny >= 0)
                map[nx][ny] ^= 1;
        }
    }
}
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment