自动搬运

查看原文

来自洛谷，原作者为

	刘辰雨 如果你不想称呼我的全名，你可以以我名称的任意非空后缀来称呼我。

搬运于2025-08-24 22:40:02，当前版本为作者最后更新于2022-09-28 13:25:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8546 小挖的 X 献身

题面：

题目传送门 （请看题面后食用此题解）

题意注意事项：

题目要求输出 “01”矩阵中由 “1” 组成的 “X” 形数量，关于 “X” 的要求题面有举例描述，值得注意的是单个的 “1” 不属于 “X” 形的范畴。

思路：

关于此题思路无外乎两点：如何判断 “X” 形和如何避免重复。

1. 如何判断 “X” 形？

如果你仔细阅读题面的样例就会发现，一个 “X” 形的长宽是一致的。 所以只需要知道一个 “X” 形的左右上角的两个 “1” ，整个 “X” 就可以被确定。所以遍历同一行的 “1” 即可。

2. 如何避免重复？

我们假象一个 “X” 形对应一个正方形，那么保证所有的正方形不重复即可。那么很容易想到，针对一个 “1” ，对其右下方所有可能符合条件的正方形进行判断，即使全部可行，也不会与之前的情况重复，因为之前的情况一定包含这个 “1” 的左方和上方部分。

代码逻辑：

既然已经解决了以上两个问题，就可以开始构建代码了。伪代码如下：

#include<头文件>
using namespace std;
判断函数（）
{
  if(确实是"X")
    答案更新
}
int main()
{
  读入；
  for(遍历每一行）
  	for（遍历每一列）
    	   if(此格为'1')
  		for(遍历与此‘1’同行的每一个‘1’)
  			调用判断函数；
  输出；
  return 0;
}

Code:

#include<cstdio>
#include<iostream>//杜绝万能头，从我做起(雾
using namespace std;
int n,mp[101][101];
char ch;
int ans;//记录答案
void pd(int i,int j,int k)
{
	
	if(n-i < k-j)
		return;
		//cout<<i<<endl; 
	int x1 = i;
	int y1 = j;
	int y2 = k;
	for(int u = 1 ; u< k-j+1 ; u++)
	{
		x1++;
		y1++;
		i++;
		y2--;
		if(mp[x1][y1] == 0)return;
		if(mp[i][y2] == 0)return;
	}//遍历“X”形，判断是否全为1，否则return
	ans++;
}
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i<= n ; i++ )
	{
		for(int j = 1 ; j<= n ; j++)
		{
			cin>>ch;
			mp[i][j] = ch-'0';
		}	
	}
	//读入
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			if(mp[i][j] == 1)
			{
				for(int k = j+1;  k <= n ; k++)
				{
					if(mp[i][k] == 1)
					{
						pd(i,j,k);
					}
				}	
			}
		}
	}//遍历并判断，记录答案
	printf("%d",ans);//输出
	return 0;//轻松结束，撒花！
} 

后记：

好久没写题解了，有什么问题请见谅。管理给个“过”，路过给个赞????~WAW