棋盘覆盖问题

问题描述

有一个边长为2的n次方的正方形棋盘，其中一个位置被图上了颜色，如图：

现在要使用角形的图案来填满这块棋盘，请问填法是什么？

示例：

主要思想

因为棋盘的边长是2的幂次，所以对半分块是很容易的，在把棋盘分成四块后，其中有一块一定被上过色，那么这时只需要放置一个角形图案到剩余的三块中间，那么这四块有可以分别视为涂过色的新棋盘，当棋盘的边长只剩2时，可以直接放置角形图案充满棋盘。因此，此题可以使用分治的思想来解决。

代码实现

每种颜色使用一个独立的整数来表示，当该颜色被使用过后，就让整数加1来代表新的颜色。

显然，当我们知道一个棋盘的初始位置和边长之后，那么棋盘的其他位置就被确定下来，因此可以用一个SubBoard类来存储这些变量。

public class Board {
    static int color = 1;
    int[][] board;
    int len;

    public Board(int a) {
        board = new int[a][a];
        len = a;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < a; j++) {
                board[i][j] = 0;
            }
        }
    }

    public void displayBoard() {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.printf("%2d ", board[i][j]);
            }
            System.out.println();
        }
    }

    public int getPos(int i, int j) {
        return board[i][j];
    }

    public void fillColor(Point pos) {
        board[pos.row][pos.col] = color;
    }

    public void fillColor(int i, int j) {
        board[i][j] = color;
    }

    public void setNewColor() {
        color++;
    }

    public void cover() {
        SubBoard subBoard = new SubBoard(new Point(0, 0), len, this);
        subBoard.cover();
    }

}

class SubBoard {
    Board board;
    Point sPos;
    int len;

    public SubBoard(Point s, int len, Board board) {
        this.sPos = s;
        this.len = len;
        this.board = board;
    }

    public void cover() {
        int sRow = sPos.row;
        int sCol = sPos.col;
        if (len == 2) {//边长为2直接填充
            for (int i = sRow; i < sRow + len; i++) {
                for (int j = sCol; j < sCol + len; j++) {
                    if (board.getPos(i, j) == 0) {
                        board.fillColor(i, j);
                    }
                }
            }
            board.setNewColor();
            return;
        }
        int subLen = len / 2;
        //划分成4个子棋盘
        SubBoard[] subBoards = new SubBoard[] { new SubBoard(new Point(sRow, sCol), subLen, board),
                new SubBoard(new Point(sRow, sCol + subLen), subLen, board),
                new SubBoard(new Point(sRow + subLen, sCol), subLen, board),
                new SubBoard(new Point(sRow + subLen, sCol + subLen), subLen, board) };
		//每个棋盘填色的位置
        Point[] fillPos = new Point[] { new Point(subBoards[0].getEndRow(), subBoards[0].getEndCol()),
                new Point(subBoards[1].getEndRow(), subBoards[1].getStartCol()),
                new Point(subBoards[2].getStartRow(), subBoards[2].getEndCol()),
                new Point(subBoards[3].getStartRow(), subBoards[3].getStartCol()) };
        for (int i = 0; i < subBoards.length; i++) {
            if (!subBoards[i].isPainted()) {
                subBoards[i].fillColor(fillPos[i]);
            }
        }
        this.setNewColor();
        for (int i = 0; i < subBoards.length; i++) {
            subBoards[i].cover();
        }
    }

    public void fillColor(Point pos) {
        board.fillColor(pos);
    }

    public void fillColor(int i, int j) {
        board.fillColor(i, j);
    }

    public void setNewColor() {
        board.setNewColor();
    }

    public int getEndRow() {
        return this.sPos.row + this.getLen() - 1;
    }

    public int getEndCol() {
        return this.sPos.col + this.getLen() - 1;
    }

    public int getStartRow() {
        return this.sPos.row;
    }

    public int getStartCol() {
        return this.sPos.col;
    }

    public int getLen() {
        return len;
    }

    public void setLen(int len) {
        this.len = len;
    }

    public Point getsPos() {
        return sPos;
    }

    public void setsPos(Point sPos) {
        this.sPos = sPos;
    }

    public boolean isPainted() {
        for (int i = sPos.row; i < sPos.row + len; i++) {
            for (int j = sPos.col; j < sPos.col + len; j++) {
                if (board.getPos(i, j) != 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Point {
    int row;
    int col;

    public Point(int r, int c) {
        row = r;
        col = c;
    }
}