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