首页 > 其他分享 >CF1375B Neighbor Grid 题解

CF1375B Neighbor Grid 题解

时间:2024-01-21 19:13:22浏览次数:31  
标签:ch 格子 int 题解 矩阵 flag Grid && CF1375B

题意简述

给你一个 $n$ 行 $m$ 列的矩阵,要求你让这个矩阵是“完美”的。

“完美”的定义如下:

  1. 若当前的格子里是一个正整数 $k$,那么与这个网格相邻(有公共边)的 $k$ 个格子也必须有一个正整数。

  2. 若当前的格子里是 $0$,那么不受上述的限制。

你可以对任意的一个格子加上 $1$,次数不受限制。

题目分析

首先,我们可以发现一个在角上的格子只有 $2$ 个格子与其相邻,在边上的只有 $3$ 个格子相邻,而在中间部分的有 $4$ 个格子相邻。如果有格子超出上述限制,因为题目规定只能增加,不能减少,所以必定无解。

接下来,我们考虑如何构造合法的矩阵。

我们考虑将整个矩阵填满,即将角上填 $2$,边上填 $3$,中间部分填 $4$,可以看出这种情况一定是“完美”的。

最后,我们考虑操作的过程是否合法。因为上述判无解的过程已经保证了给出矩阵的数一定小于等于矩阵填满后的数,所以不会出现减少的情况,故合法。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int T,n,m,a[N][N];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=(x<<1)+(x<<3)+ch-48;
	    ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void solve()
{
	n=read();
	m=read();
	bool flag=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
			if((i==1||i==n)&&(j==1||j==m)&&a[i][j]>2) flag=1;
			if((i==1||i==n)&&(j>1&&j<m)&&a[i][j]>3) flag=1;
			if((j==1||j==m)&&(i>1&&i<n)&&a[i][j]>3) flag=1;
			if(j>1&&j<m&&i>1&&i<n&&a[i][j]>4) flag=1; 
		}
	}
	if(flag)
	{
		printf("NO\n");
		return;
	}
	printf("YES\n");
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
		    if((i==1||i==n)&&(j==1||j==m)) a[i][j]=2;
			if((i==1||i==n)&&(j>1&&j<m)) a[i][j]=3;
			if((j==1||j==m)&&(i>1&&i<n)) a[i][j]=3;
			if(j>1&&j<m&&i>1&&i<n) a[i][j]=4; 
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			write(a[i][j]);
			printf(" ");
		}
		printf("\n");
	}
}
int main()
{
	T=read();
	while(T--)
	{
		solve();
	}
	return 0;
}

标签:ch,格子,int,题解,矩阵,flag,Grid,&&,CF1375B
From: https://www.cnblogs.com/zhuluoan/p/17978174

相关文章

  • P5362 [SDOI2019] 连续子序列 题解--zhengjun
    题面传送门提供一种和其他题解完全不同的解法。记\(P_0\)为题中给出的序列,\(P_1\)为\(P_0\)取反的结果。记\(S_{l\simr}\)表示\(S_lS_{l+1}\dotsS_{r}\)。方便起见,\(P\)下标从\(0\)开始,其余的串都是从\(1\)开始。这里用\(P_{0,i}=\operatorname{popcount(i)}......
  • Github图床搭建,结合Picgo与jsdelivr的免费cdn加速,以及部分问题解决方案
    留份文档,便于后续查询===================用到的地址:Github:GitHubPicgo:PicGoisHere|PicGojsdelivr加速地址:https://cdn.jsdelivr.net/gh/Github用户名/仓库名@master===================1.创建一个GitHub仓库:进入你的GitHub首页,在右上角你会找到一个➕,在下拉菜单中......
  • P7192 [COCI2007-2008#6] GEORGE 题解
    题目简述给定一张$n$个点$m$条边的无向图,从$u_i\rightarrowv_i$需要用时$w_i$分钟。有一位T先生从$0$时刻按有$g$个点的序列顺序移动,即$v_1\rightarrowv_2\rightarrow\cdots\rightarrowv_g$。还有一位卡车司机Luka从$k$时刻开始从$a$点出发,Luka不......
  • 洛谷 P9843 [ICPC2021 Nanjing R] Paimon Sorting 题解
    Descirption给出一个排序算法(用伪代码表示):SORT(A)forifrom1tonforjfrom1tonifa[i]<a[j]Swapa[i]anda[j]算出对于一个序列\(A=a_1,a_2,\cdots,a_n\)的所有前缀\(A_k=a_1,a_2,\cdots,a_k\)(\(1\lek\len\)),\(\operatorname{SORT}(A_......
  • AT_abc337_d 的题解
    AT_abc337_d的题解题目大意给你一个\(H\timesW(H\timesW\leq2\times10^5)\)的矩阵,矩阵由o、x和.构成。存在一种操作:将一个.变成o。问在一段连续的区间内,需要进行多少次操作才可以将同一行或同一列中的连续\(k\)个数都变为o,若无法完成,输出-1。思考过程看......
  • AT_abc337_c的题解
    AT_abc337_c的题解题目大意就是给你一个数组$a=(a_1,a_2,\ldots,a_n)$,若$a_i$为$-1$,那么这个数的下标就是输出序列的开头,否侧,这个数在输出序列中排在$a_i$的下一个。思考过程从样例中不难发现:$1,2,\ldots,n$中的每一个数最多在$a$中出现一次;输出序列中的每一个......
  • P10073 [GDKOI2024 普及组] 刷野 II 的题解
    P10073[GDKOI2024普及组]刷野II的题解谨以此篇题解记录我考场上唯一通过的一题~解题思路可以考虑定义两个指针x和y,分别为左侧攻击到哪里和右侧。此时,从两侧线性想中间递推,若先打左边的代价小就打左边的,否则就打右边的。按照这个方法向中间推就可以了。Code#include<......
  • ABC337 E Bad Juice 题解
    QuestionABC337EBadJuice交互题\(n\)瓶果汁中有\(1\)瓶是坏的,现在需要把这些果汁分给\(m\)个人,每个人可以喝任意瓶,然后通过\(m\)个人的回复判断哪一瓶是坏的需要输出最小的\(m\)以及坏果汁的编号Solution\(m\)返回的结果由\(01\)构成,自然而然想到二进制,考虑......
  • ABC337 D Cheating Gomoku Narabe 题解
    QuestionABC337DCheatingGomokuNarabe给出一个\(H\timesW\)的矩阵,由o,x,.组成,一次操作为把一个.变成o,问需要最少多少次操作使得横着或竖着有连续的\(K\)个oSolution先来考虑只有一行的情况,我们定义一个长度为\(K\)的"窗口",假设需要把这个"窗口"里面的所有......
  • CF526F Pudding Monsters 题解
    题目链接:CF或者洛谷析合树真是连续段问题的降智神器先看下题目的一些特殊性,每行每列恰好有一个棋子。考虑特殊性,\(n\timesn\)的棋盘,那么就该判断是否有\(n\)个棋子,容易观察到,也就是相当于每一行并且每一列都有一个棋子。而容易知道,这些棋子所在的行或者列拿出来应当是“......