116. 飞行员兄弟（Acwing）（递归+位运算）

116. 飞行员兄弟

题目链接：

https://www.acwing.com/problem/content/118/

题解：

1、递归：

递归的最难理解的点就是要从满足题目的从左向右，从上到下，所以遇到y == 4的边界时，就应该跳到下一行的第一个位置，注意恢复现场。

2、位运算：

和95、费解的开关差不多，但是这里是穷举2^16种可能，直接判断，利用getValue(int x, int y)将物理一维转化为二维的穷举。

AC代码：

1、递归

public class NO116 {
    static char[][] arr = new char[4][4];
    static LinkedList<Pair> res = new LinkedList<>();
    static Pair[] pairRes = null;
    static int step = 1000;

    static void turn(int x, int y) {
        for (int i = 0; i < 4; i++) {
            arr[x][i] ^= 1;
            arr[i][y] ^= 1;
        }
        arr[x][y] ^= 1;
    }

    static void dfs(int x, int y ) {
        if (x == 3 && y == 4) {
            boolean flag = true;
            pos:
            for (int i = 0 ;i < 4;i++) {
                for (int j = 0;j<4;j++) {
                    if (arr[i][j] == '0'){
                        flag = false;
                        break pos;
                    }
                }
            }
            if (flag && res.size() < step) {
                step = res.size();
                pairRes = res.toArray(new Pair[0]);
            }
            return;
        }
        if (y == 4) { // 从左向右，从上到下
            x = x+1;
            y = 0;
        }
        // 操作门把手
        turn(x,y);
        res.push(new Pair(x+1,y+1));
        dfs(x,y+1);
        // 恢复现场
        turn(x,y);
        res.pop();
        // 不操作门把手
        dfs(x,y+1);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            arr[i] = sc.next().toCharArray();
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) arr[i][j] = arr[i][j] == '-' ? '1' : '0';
        }
        dfs(0,0);
        System.out.println(step);
        for (int i = pairRes.length-1; i >= 0; i--) {
            System.out.println(pairRes[i].x + " " + pairRes[i].y);
        }
    }
}

class Pair {
    int x, y;
    public Pair() {}
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

2、位运算

public class NO116 {
    static char[][] arr = new char[4][4];
    static char[][] temp = new char[4][4];
    static List<Pair> res = new ArrayList<>();
    static Pair[] pairRes = null;
    static int step = 1000;

    static int getValue(int x,int y) {
        return x*4 + y;
    }

    static void turn(int x, int y) {
        for (int i = 0; i < 4; i++) {
            arr[x][i] ^= 1;
            arr[i][y] ^= 1;
        }
        arr[x][y] ^= 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            arr[i] = sc.next().toCharArray();
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) arr[i][j] = arr[i][j] == '-' ? '1' : '0';
        }
        for (int op = 0;op < 1<<16;op++) {
            for (int i = 0;i <4;i++) temp[i] = Arrays.copyOf(arr[i],arr[i].length);
            res.clear();
            for (int i = 0;i < 4;i++) {
                for (int j = 0;j < 4;j++) {
                    if( (op >> getValue(i,j) & 1) == 1) {
                        turn(i,j);
                        res.add(new Pair(i+1,j+1));
                    }
                }
            }
            boolean flag = true;
            pos:
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (arr[i][j] == '0') {
                        flag = false;
                        break pos;
                    }
                }
            }
            if (flag && res.size() < step) {
                step = res.size();
                pairRes = res.toArray(new Pair[0]);
            }
            for (int i = 0;i <4;i++) arr[i] = Arrays.copyOf(temp[i],temp[i].length);
        }


        System.out.println(step);
        for (int i = 0; i < pairRes.length; i++) {
            System.out.println(pairRes[i].x + " " + pairRes[i].y);
        }
    }
}

class Pair {
    int x, y;
    public Pair() {}
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}