棋盘覆盖

电玩女神 2024-04-18 17:06 112阅读 0赞

给出一个2的k次方乘以2的k次方的棋盘，并任意给出一个奇异点（棋盘中一个位置），用L型（占3个格）给他铺满除奇异点以外的区域，要求不能重复。就好像下面那样（贼拉丑）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70][]

思路：

采用分治的思路，将棋盘分区不断缩小，每次涂没有涂过的3个面挨着分界线的交点的那几块。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70 1][]

红的像屎一样的那个是奇异点，红色线条是第一次分块，分完后，涂1的块。

然后再把分的4个块再分，黄色的线是第二次分块，分完后，涂2的块。

代码实现（纯属为了找到方便起的中文类名）：

package 算法课;
    
    public class 棋盘覆盖 {
    	int[][] board;
    
    	public 棋盘覆盖(int[][] board) {
    		this.board = board;
    	}
    
    	/*
    	 * tr 行号 td 列号 dr 特殊元素所在的行号 dc 特殊元素所在的列号 size 棋盘规模
    	 */
    	void ChessBoard(int[][] board, int tr, int tc, int dr, int dc, int size,int num) {
    		// 分割棋盘
    		size = size / 2;
    		num++;
    		if (size == 0) {
    			return;
    		}
    		// 在二象限
    		if (dr <= tr && dc <= tc) {
    			ChessBoard(board, tr - size / 2, tc - size / 2, dr, dc, size,num);
    		} else {
    			board[tr][tc] = num;
    			ChessBoard(board, tr - size / 2, tc - size / 2, tr, tc, size,num);
    		}
    		// 第一象限
    		if (dr <= tr && dc > tc) {
    			ChessBoard(board, tr - size / 2, tc + size / 2, dr, dc, size,num);
    		} else {
    			board[tr][tc + 1] = num;
    			ChessBoard(board, tr - size / 2, tc + size / 2, tr, tc + 1, size,num);
    		}
    		// 第三象限
    		if (dr > tr && dc <= tc) {
    			ChessBoard(board, tr + size / 2, tc - size / 2, dr, dc, size,num);
    		} else {
    			board[tr + 1][tc] = num;
    			ChessBoard(board, tr + size / 2, tc - size / 2, tr + 1, tc, size,num);
    		}
    		// 第四象限
    		if (dr > tr && dc > tc) {
    			ChessBoard(board, tr + size / 2, tc + size / 2, dr, dc, size,num);
    		} else {
    			board[tr + 1][tc + 1] = num;
    			ChessBoard(board, tr + size / 2, tc + size / 2, tr + 1, tc + 1, size,num);
    		}
    	}
    
    	public static void main(String[] args) {
    		int[][] board = new int[9][9];
    		棋盘覆盖 t = new 棋盘覆盖(board);
    		int tr = (board.length - 1) / 2;
    		int tc = tr;
    		t.ChessBoard(board, 4, 4, 2, 2, 8,1);
    		for (int i = 1; i <= board.length - 1; i++) {
    			for (int j = 1; j <= board[0].length - 1; j++) {
    				System.out.print(board[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    }

注意我的数组忽略的0的那一行以及那一列，直接1开始的。

结果：

4 4 4 4 4 4 4 4 
    4 0 3 4 4 3 3 4 
    4 3 3 4 4 4 3 4 
    4 4 4 4 2 4 4 4 
    4 4 4 2 2 4 4 4 
    4 3 4 4 4 4 3 4 
    4 3 3 4 4 3 3 4 
    4 4 4 4 4 4 4 4

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8f6949a03c134c2fb63886a12c6ce55f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d5895b044f89405e98b58e63f1517444.png