题目翻译:
有 $n \times n$ 大小的棋盘,一共放 $k$ 辆车,使得这个棋盘稳定。
稳定的概念是:所有的车移动至相邻四格(上下左右)不会出现一行一列有 $\ge 2$ 辆车。
做题思路:
我们可以考虑,移动之后没有同一行一列有多辆车,那么就让它移动之后还是只有它一辆车,换句话说,每辆车之间至少空一行和一列,也就是在对角线上放是最优想法。如果对角线放不下 $k$ 辆车了,无解输出 -1
。
深入思考(此分析大佬跳过)
在怎样的情况下 $n \times n$ 的棋盘放不下 $k$ 辆车呢?
很显然,每两行两列放一辆车,那么最多可以放 $\left\lfloor\dfrac{n+1}{2}\right\rfloor$ 辆车(大多数语言整数除法自动下取整),所以只要判断 $\dfrac{n+1}{2}$ 与 $k$ 的大小关系。
AC代码
void solve()
{
int n,k;
cin>>n>>k;
if((n+1)/2<k)//判断是否放得下
{
cout<<-1<<endl;
return;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j&&i%2!=0&&k>0)//判断分别为:对角线、隔一行一列、还可以放车
{
cout<<'R';
k--;//放完一辆
}
else
{
cout<<'.';
}
}
cout<<endl;
}
}
多组数据,代码未全。请勿copy,当心踩坑!