[蓝桥杯 2023 国 A] 01 游戏

Luogu

IDLGP10419

Time1000ms

Memory256MB

DifficultyP4

2023深度优先搜索 DFS剪枝蓝桥杯国赛

小蓝最近玩上了 $01$ 游戏，这是一款带有二进制思想的棋子游戏，具体来说游戏在一个大小为 $N\times N$ 的棋盘上进行，棋盘上每个位置都需要放置一位数字 $0$ 或者数字 $1$，初始情况下，棋盘上有一部分位置已经被放置好了固定的数字，玩家不可以再进行更改。玩家需要在其他所有的空白位置放置数字，并使得最终结果满足以下条件： 1. 所有的空白位置都需要放置一个数字 $0/1$； 2. 在水平或者垂直方向上，相同的数字不可以连续出现大于两次； 3. 每一行和每一列上，数字 $0$ 和数字 $1$ 的数量必须是相等的 (例如 $N=4$，则表示每一行/列中都需要有 $2$ 个 $0$ 和 $2$ 个 $1$)； 4. 每一行都是唯一的，因此每一行都不会和另一行完全相同；同理每一列也都是唯一的，每一列都不会和另一列完全相同。现在请你和小蓝一起解决 $01$ 游戏吧！题目保证所有的测试数据都拥有一个唯一的答案。 ## Input 输入的第一行包含一个整数 $N$ 表示棋盘大小。接下来 $N$ 行每行包含 $N$ 个字符，字符只可能是 `0`、`1`、`_` 中的其中一个 (ASCII 码分别为 $48$，$49$，$95$)，`0` 表示这个位置数字固定为 $0$，`1` 表示这个位置数字固定为 $1$，`_` 表示这是一个空白位置，由玩家填充。 ## Output 输出 $N$ 行每行包含 $N$ 个字符表示题目的解，其中的字符只能是 `0` 或者 `1`。 [samples] ## Note **【评测用例规模与约定】** 对于 $60\%$ 的评测用例，$2\le N\le 6$; 对于所有评测用例，$2\le N\le 10$，$N$ 为偶数。感谢 @rui_er 提供测试数据。

Samples

Input #1

6
_0____
____01
__1__1
__1_0_
______
__1___

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2023 国 A] 01 游戏",
    "description": {
      "content": "小蓝最近玩上了 $01$ 游戏，这是一款带有二进制思想的棋子游戏，具体来说游戏在一个大小为 $N\\times N$ 的棋盘上进行，棋盘上每个位置都需要放置一位数字 $0$ 或者数字 $1$，初始情况下，棋盘上有一部分位置已经被放置好了固定的数字，玩家不可以再进行更改。玩家需要在其他所有的空白位置放置数字，并使得最终结果满足以下条件： 1. 所有的空白位置都需要放置一个数字 $0/1$； 2. 在",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10419"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝最近玩上了 $01$ 游戏，这是一款带有二进制思想的棋子游戏，具体来说游戏在一个大小为 $N\\times N$ 的棋盘上进行，棋盘上每个位置都需要放置一位数字 $0$ 或者数字 $1$，初始情况下，棋盘上有一部分位置已经被放置好了固定的数字，玩家不可以再进行更改。玩家需要在其他所有的空白位置放置数字，并使得最终结果满足以下条件：\n\n1. 所有的空白位置都需要放置一个数字 $0/1$；\n2. 在...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments