Java实现4×4棋盘2×1/1×2砖块放置问题求助

问题概述 #

给定4×4的棋盘，输入由0和1组成的字符串（长度≤1000）：

• 0代表2×1的竖砖，需占据同一列的上下两个单元格
• 1代表1×2的横砖，需占据同一行的左右两个单元格
  要求按字符串顺序放置砖块，不可叠放；每放置一块砖后，若某行/列被完全占据，则释放该行/列的所有单元格（可能导致已放置的砖块只剩一半留在棋盘）。最终为每个砖块输出其放置时的最小行、列坐标（1-based，即行、列范围1~4）。

核心实现思路 #

1. 棋盘状态管理

   • 用boolean[4][4]数组表示棋盘，true表示单元格被占用，false表示空闲，初始所有单元格均为空闲状态。

2. 砖块放置规则

   • 按从上到下、从左到右的顺序遍历棋盘，找到第一个能放下当前砖块的合法位置：
     • 竖砖（0）：需满足当前单元格(r,c)和下方单元格(r+1,c)均空闲，且r+1 < 4（避免越界）
     • 横砖（1）：需满足当前单元格(r,c)和右侧单元格(r,c+1)均空闲，且c+1 <4（避免越界）
   • 找到位置后，标记对应单元格为占用状态，并记录该位置的1-based坐标（数组0-based转1-based只需行、列各加1）。

3. 行/列释放逻辑

   • 放置完砖块后，立即检查所有行和列：
     • 遍历每一行，若该行所有单元格均为true，则将该行所有单元格重置为false（释放整行）
     • 遍历每一列，若该列所有单元格均为true，则将该列所有单元格重置为false（释放整列）
   • 注意：释放操作会影响后续砖块的放置，但不改变当前砖块的输出坐标。

Java代码实现 #

import java.util.Scanner;

public class BrickPlacement {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        scanner.close();

        // 初始化棋盘，false表示空闲
        boolean[][] board = new boolean[4][4];

        for (char brick : input.toCharArray()) {
            int placedR = -1;
            int placedC = -1;

            // 寻找最小位置放置砖块
            for (int r = 0; r < 4; r++) {
                for (int c = 0; c < 4; c++) {
                    if (brick == '0') {
                        // 竖砖：需要当前和下方单元格空闲，且不越界
                        if (r + 1 < 4 && !board[r][c] && !board[r+1][c]) {
                            board[r][c] = true;
                            board[r+1][c] = true;
                            placedR = r + 1; // 转1-based
                            placedC = c + 1;
                            break;
                        }
                    } else {
                        // 横砖：需要当前和右侧单元格空闲，且不越界
                        if (c + 1 < 4 && !board[r][c] && !board[r][c+1]) {
                            board[r][c] = true;
                            board[r][c+1] = true;
                            placedR = r + 1;
                            placedC = c + 1;
                            break;
                        }
                    }
                }
                if (placedR != -1) {
                    break;
                }
            }

            // 输出当前砖块的放置坐标
            System.out.println(placedR + " " + placedC);

            // 检查并释放满行
            for (int r = 0; r < 4; r++) {
                boolean rowFull = true;
                for (int c = 0; c < 4; c++) {
                    if (!board[r][c]) {
                        rowFull = false;
                        break;
                    }
                }
                if (rowFull) {
                    for (int c = 0; c < 4; c++) {
                        board[r][c] = false;
                    }
                }
            }

            // 检查并释放满列
            for (int c = 0; c < 4; c++) {
                boolean colFull = true;
                for (int r = 0; r < 4; r++) {
                    if (!board[r][c]) {
                        colFull = false;
                        break;
                    }
                }
                if (colFull) {
                    for (int r = 0; r < 4; r++) {
                        board[r][c] = false;
                    }
                }
            }
        }
    }
}

示例验证 #

输入010时，代码执行流程：

1. 处理第一个0：找到(0,0)（0-based）位置放置竖砖，输出1 1；无满行/列，棋盘状态为(0,0)、(1,0)占用。
2. 处理第二个1：找到(0,1)位置放置横砖，输出1 2；无满行/列，棋盘新增(0,1)、(0,2)占用。
3. 处理第三个0：找到(0,3)位置放置竖砖，输出1 4；此时第一行所有单元格均被占用，释放第一行，棋盘第一行恢复空闲。

内容的提问来源于stack exchange，提问作者Yury