【题解】「CF1182B」Plus from Picture

这是一道超级水的模拟 + 简单搜索。

说说思路：

先找到中心点，就是自己和上下左右都为 * 的。

上下左右上的所有 * 都删掉，然后再看看有没有多余的 * 如果有输出 NO 否则输出 YES。

比如说有这样一个 \(n = 5\) 的图：

\[\begin{matrix}
.&.&.&.&*\\
.&.&*&.&.\\
.&*&*&*&*\\
.&.&*&.&.\\
.&.&*&.&.
\end{matrix}\]

首先一个一个找，当找到一个点，自己本身和上下左右均为 \(*\) 时（如图中 \(a\) 点）：

\[\begin{matrix}
.&.&.&.&*\\
.&.&*&.&.\\
.&*&a&*&*\\
.&.&*&.&.\\
.&.&*&.&.
\end{matrix}\]

将上下左右上的一条全部变为 \(*\)：

\[\begin{matrix}
.&.&.&.&*\\
.&.&.&.&.\\
.&.&.&.&.\\
.&.&.&.&.\\
.&.&.&.&.
\end{matrix}\]

那我们就会发现图中还有 \(*\) 没有变成 \(.\) 这就说明此加号不合法。

上代码：

/*

  Problem:CF1182B

  Date:14/06/20 12:02

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<string>

#define line cout << endl

#define int long long

using namespace std;

char ma[2005][2005];

int h, w;

bool flag;

void up (int i, int j) {

	ma[i][j] = '.';

	if (ma[i - 1][j] == '*')

		return up(i - 1, j);

}

void down (int i, int j) {

	ma[i][j] = '.';

	if (ma[i + 1][j] == '*')

		return down(i + 1, j);

}

void left (int i, int j) {

	ma[i][j] = '.';

	if (ma[i][j - 1] == '*')

		left(i, j - 1);

}

void right (int i, int j) {

	ma[i][j] = '.';

	if (ma[i][j + 1] == '*')

		return right(i, j + 1);

}

void kill (int i, int j) {

	ma[i][j] = '.';

	up (i - 1, j);

	down (i + 1, j);

	left (i, j - 1);

	right (i, j + 1);

}

void test () {//测试(i,j)是不是一个加号的中心

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

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

            if (ma[i][j] == '*' &&

                ma[i - 1][j] == '*' &&

                ma[i][j - 1] == '*' &&

                ma[i + 1][j] == '*' &&

                ma[i][j + 1] == '*') {//对第一个可能的十字的中心

	            	kill (i, j);//抹去这个十字

	                flag = true;

	                break;

            }

        if (flag) break;

    }

    for (int i = 1; i <= h; i++)//这时,应没有'*'了

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

            if (ma[i][j] == '*')

                flag = false;

}

signed main () {

	cin >> h >> w;

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

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

			cin >> ma[i][j];

	test();

	if(flag) puts("YES");

	else puts("NO");

	return 0;

}

谢谢。

巴特西

【题解】「CF1182B」Plus from Picture

最新文章

热门文章