P3755 题解 | MingDynasty

题目描述

在一个 n×n 的棋盘上，有 k 个格子有障碍物（位于主对角线上）。现在要用 1×2 的骨牌覆盖棋盘，要求骨牌不能重叠，也不能覆盖到有障碍物的格子上。请输出一种覆盖方案，用数字表示不同的骨牌。

输入格式

第一行两个整数 n, k (1 ≤ n ≤ 500, 0 ≤ k ≤ n)

接下来 k 行，每行一个整数，表示障碍物的行号（列号与行号相同）

输出格式

输出一个 n×n 的矩阵，表示覆盖方案。每个骨牌用相同的数字表示，数字从1开始递增。障碍物位置输出0。

算法思路

本题可以采用贪心策略解决：

初始化棋盘，标记所有障碍物位置（主对角线上的k个格子）
按行优先顺序遍历棋盘每个格子
对于每个未被覆盖且无障碍的格子：
- 优先尝试向右放置横骨牌（如果右边格子存在且未被覆盖）
- 如果无法向右放置，则尝试向下放置竖骨牌（如果下边格子存在且未被覆盖）
使用计数器为每个骨牌分配唯一编号

这种贪心策略能够保证在题目限制下找到一种可行的骨牌覆盖方案。

代码实现


#include<bits/stdc++.h>

using namespace std;

int n,k,ans[555][555];

bool vis[555][555];

int main(){

  cin.tie(0)->sync_with_stdio(0);

  cin>>n>>k;

  for(int i=1;i<=k;i++) vis[i][i]=1;

  int cnt=1;

  for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

      if(!vis[i][j]){

        if(j+1<=n&&!vis[i][j+1]) 

          ans[i][j]=ans[i][j+1]=cnt++,vis[i][j]=vis[i][j+1]=1;

        else if(i+1<=n&&!vis[i+1][j]) 

          ans[i][j]=ans[i+1][j]=cnt++,vis[i][j]=vis[i+1][j]=1;

      }

  for(int i=1;i<=n;i++){

    for(int j=1;j<=n;j++) cout<<ans[i][j]<<' ';

    cout<<'\n';

  }

  return 0;

}

示例分析

假设输入 n=3, k=1，障碍物在(1,1)位置：

坐标	(1,1)	(1,2)	(1,3)
(2,1)	(2,2)	(2,3)
(3,1)	(3,2)	(3,3)

可能的输出方案：

0	1	1
2	2	3
3	4	4

其中数字相同的格子表示同一块骨牌覆盖的位置。