Blog

棋盘翻转

Fliptile

Posted by BY on September 9, 2019

前言

猛起更新。

正文

问题来源

今天心情不是很好，好友给我出了一道题让我转移一下注意力。

问题描述

给你一个棋盘，上面摆满了棋子。这些棋子有两面，一面是黑色，一面是白色。初始状态已经给出，0代表白色，1代表黑色。
当你翻转一个棋子的时候，也会翻转与这个棋子相邻(斜相邻不计入)的所有棋子。问你每个位置最少需要多少次翻转，才能将这个棋盘全部翻转成白色。输出所有方案中字典序最小的那个（即是翻转次数最小的那个）。如果没有的话，输出不可能。

示例 1:

输入： board =
[
  ['b','w','w','b'],
  ['b','b','w','b'],
  ['b','w','w','b'],
  ['b','w','w','w']
]
输出： 4

分析：

const (
    bwm_row = 4
    bwm_col = 4
    points = bwm_row * bwm_col
)

func allSameColor(bwm [][]byte) bool {
    firstColor := bwm[0][0]
    for i := 0; i < len(bwm); i++ {
        for j := 0; j < len(bwm[0]); j++ {
            if bwm[i][j] != firstColor {
                return false
            }
        }
    }
    return true
}

func cellReverseColor(cell *byte) {
    if *cell == 'b' {
        *cell = 'w'
    } else {
        *cell = 'b'
    }
}

func reverseColor(bwm [][]byte, position int) {
    row := position / bwm_col
    col := position % bwm_col
    cellReverseColor(&bwm[row][col])
    if col - 1 >= 0 {
        cellReverseColor(&bwm[row][col-1])
    }
    if col + 1 < bwm_col {
        cellReverseColor(&bwm[row][col+1])
    }
    if row - 1 >= 0 {
        cellReverseColor(&bwm[row-1][col])
    }
    if row + 1 < bwm_row {
        cellReverseColor(&bwm[row+1][col])
    }
}

func minReverse(bwm [][]byte) int {
    min := math.MaxInt32
    dfs(bwm, 0, 0, &min)
    return min
}

func dfs(bwm [][]byte, position, count int, min *int)  {
    if position == points {
        if allSameColor(bwm) == true {
            *min = count
        }
        return
    }
    if count < *min {
        reverseColor(bwm, position)
        dfs(bwm, position+1, count+1, min)
        reverseColor(bwm, position)
        dfs(bwm, position+1, count, min)
    }
}

func main() {
   bwm := [][]byte{
        {'b', 'w', 'w', 'b'},
        {'b', 'b', 'w', 'b'},
        {'b', 'w', 'w', 'b'},
        {'b', 'w', 'w', 'w'},
    }
   ret := minReverse(bwm)
   if ret == math.MaxInt32 {
        fmt.Println("IMPOSSIBLE")
   } else {
        fmt.Println(ret)
   }
}

好友给我传来的答案
严格控制翻转步数

#include <iostream>
#include <cstdlib>

using namespace std;

bool map[6][6], Find = false;
int step;
int dr[5] = {-1, 0, 0, 0, 1};
int dc[5] = {0, -1, 0, 1, 0};
bool OK() {
    for(int i = 1; i <= 4; i++) {
        for(int j = 1; j <= 4; j++) {
            if(map[i][j] != map[1][1]) {
                return false;
            }
        }
    }
    return true;
}

void flip(int row, int col) {
    for(int i = 0; i < 5; i++) {
        int x = row + dr[i];
        int y = col + dc[i];
        map[x][y] = !map[x][y];
    }
}

void dfs(int row, int col, int dep) {
    if (dep == step) {
        Find = OK();
        return;
    }
    if (Find|| row == 5) {
        return;
    }
    flip(row, col);
    if (col < 4) {
        dfs(row, col + 1, dep + 1);
    } else {
        dfs(row + 1, 1, dep + 1);
    }
    flip(row, col);
    if (col < 4) {
        dfs(row, col + 1, dep);
    } else {
        dfs(row + 1, 1, dep);
    }
}

int main() {
    char c;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            cin >> c;
            if (c == 'b') {
                map[i][j] = true;
            }
        }
    }
    for (step = 0; step <= 16; step++) {
        dfs(1, 1, 0);
        if(Find) {
            break;
        }
    }
    if (Find) {
        cout << step << endl;
    } else {
        cout << "Impossible" << endl;
    }
    return 0;
}

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog