CF389B Fox and Cross

洛谷题面

题目大意

有一个 \(n\times n\) 的矩阵,每个点为 .# ,问该矩阵是否能够分解成多个如下图的由 # 组成的十字形:

x # x
# # #
x # x

x 表示任意字母。

题目分析

直接模拟。

读入字符数组后,按顺序遍历每个点,判断该点是否为十字形,如果是,则把它们改为 .,这样就避免了重复的问题。

当然也可以用一个标记数组来表示该十字形是够被算过。

注意一下边界问题即可。

代码

//2021/11/17

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() std::ios::sync_with_stdio(false)

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=105;

char mp[ma][ma];

int n;

inline bool calc(int x,int y)
{
	return (mp[x][y]=='#' && mp[x-1][y]=='#' && mp[x+1][y]=='#' && mp[x][y-1]=='#' && mp[x][y+1]=='#');
}

inline void solve(int x,int y)
{
	mp[x][y]=mp[x-1][y]=mp[x][y-1]=mp[x+1][y]=mp[x][y+1]='.';
}

int main(void)
{
	n=read();
	
	for(register int i=0;i<n;i++)
	{
		scanf("%s",mp[i]);
	}
	
	for(register int i=1;i<n-1;i++)
	{
		for(register int j=1;j<n-1;j++)
		{
			if(calc(i,j)==true)
			{
				solve(i,j);
			}
		}
	}
	
	for(register int i=0;i<n;i++)
	{
		for(register int j=0;j<n;j++)
		{
			if(mp[i][j]=='#')
			{
				puts("NO");
				
				return 0;
			}
		}
	}
	
	puts("YES");
	
	return 0;
}
上一篇:推荐系统 之 Wide&Deep和Deep&Cross


下一篇:That Nice Euler Circuit——Regionals 2004 >> Asia - Shanghai——UVALive - 3263