P9567 [SDCPC2023] L-Puzzle: Sashigane_l. puzzle: sashigane

去洛谷看我的博客

思路

刚看到还被吓了一跳，以为又是什么神仙题目，细想了一下觉得有做头。

Step1.不算很好的解法

首先想到左下一个右上一个，就可以套一圈，然后就可以先套一个正方形出来，这个正方形可以尽可能的大，如下图的红色框。

然后就剩下三种情况：

1. 刚好覆盖完（即黑色方格恰好在正中间），输出就完事儿。
2. 留下两边，直接对角输出就完事儿，剩多少就输出多少。
3. 留下三边，这样就剩下两个对角，先从一个对角输出，然后从另一个对角输出。

如上图，红色方格代表套出的正方形，左侧为第二种情况，右侧为第三种情况。

想法很不错（至少当时我是这么觉得的），然后实现了很久，居然 WA 了。

对了，顺带一提，设套出的正方形边长为 $k$，再令 $sum=\frac{k-1}{2}$，那么套出的正方形有 $2\times sum$ 个 L 形，还剩下 $n-2\times sum-1$ 个空行或者空列，也就是还剩下 $n-2\times sum-1$ 个 L 形。

所以一共会放 $n-1$ 个 L 形。

如果想看这个做法的代码，很抱歉，我实在不想去调了，想看可以看这个屎山代码。

Step2.逐步扩展的正方形

抛弃了上面的做法后，我就跑去看其他题了，然后突然就想到了一个很不错的方法。

倒过来想，我们如何把一个完整的正方形通过切割 L 形，变成只有 $1\times 1$ 的黑色方格呢？

可以每次从边角切一个 L 形，就变成了一个边长小 $1$ 的小正方形，然后逐步朝黑色方格切割，最后就可以边长黑色方格。

我们再反过来，每次从当前正方形的四个角添一个正方形就可以了，直到添成 $n\times n$ 的大正方形。

每次边长大 $1$，所以需要 $n-1$ 次，这个方法的总次数比上一个方法好理解一些。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,x,y,xx,xxx,yy,yyy;
int main()
{
	scanf("%d%d%d",&n,&x,&y);
	printf("Yes\n%d\n",n-1);//直接得出答案
	xx=xxx=x,yy=yyy=y;//记录边界，用xx，xxx之类的绝对不是因为x1,x2,y1,y2是关键字CE了qwq
	for(int i=1;i<n;++i)
	{
		if(xx>1&&yy>1) printf("%d %d %d %d\n",--xx,--yy,i,i);//如果可以从这个方向添L形，下面同理
		else if(xx>1&&yyy<n) printf("%d %d %d %d\n",--xx,++yyy,i,-i);
		else if(xxx<n&&yy>1) printf("%d %d %d %d\n",++xxx,--yy,-i,i);
		else printf("%d %d %d %d\n",++xxx,++yyy,-i,-i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16