P8546题解

· · 题解

P8546 小挖的 X 献身

题面：

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

题意注意事项：

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

思路：

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

  1. 如何判断 “X” 形？

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

  1. 如何避免重复？

我们假象一个 “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