4 条题解

  • 5
    @ 2023-8-20 12:49:07

    思路:

    1. 输入数据。

    2. 遍历提供的图。

    3. 如果,遍历到的点是'#'(也就是这有可能是钻石的最上方的点)。

      1. 寻找与'#'对应的'#'(也就是寻找对应钻石最下面的点)。 注:如果找不到,也就找到点的x坐标超限了,或是两点之差为奇数,就无法组成菱形。
      2. 根据最上面的点和最下面的点,我们已经可以确定出菱形的形状,我们要判断实际的菱形边界是否和我们模拟的菱形一样。
      3. 我们要判断菱形内部是否都是'.',如果都是,那么他就是一个钻石。
      4. 如果它符合上面三个条件,那么计数器加一。
    4. 遍历完后,输出计数器的值。


    思路实现不难,但难的是弄细节,我整整改了一个上午。


    AC代码(求赞)(我自认为格式还是蛮清晰的)

    #include <bits/stdc++.h>
    using namespace std;
    int n,m,cnt;
    char s[2005][2005];//储存输入
    bool z1,z2;//记录3.2,3.3步是否成立
    int sou(int x,int y)
    {//根据钻石的顶点搜索钻石的低点(3.1步)。
        x++;
        while (s[x][y]=='.' && x<=n)
            x++;
        return x;//返回低点
    }
    bool panb(int i,int i2){
        return (i>=1 && i2>=1 && i<=n && i2<=m);
    }//判断是否超出边界。
    bool panbian(int sx,int ex,int y)
    {//判断菱形四条边是否都是'#'。(3.2步)
        int mid=(ex-sx)/2+sx;//用于分割菱形的四条边
        for (int i=sx,i2=y;i<=mid;i++,i2--)
            if (s[i][i2]=='.' || !panb(i,i2))//如果超出边界或不是'#'。
                return false;
        //判断菱形左上边。
        for (int i=sx,i2=y;i<=mid;i++,i2++)
            if (s[i][i2]=='.' || !panb(i,i2))//如果超出边界或不是'#'。
                return false;
        //判断菱形右上边。
        for (int i=ex,i2=y;i>=mid;i--,i2--)
            if (s[i][i2]=='.' || !panb(i,i2))//如果超出边界或不是'#'。
                return false;
        //判断菱形左下边。
        for (int i=ex,i2=y;i>=mid;i--,i2++)
            if (s[i][i2]=='.' || !panb(i,i2))//如果超出边界或不是'#'。
                return false;
        //判断菱形左下边。
        return true;//如果4条件都符合,边界条件就成立。
    }
    bool pannei(int sx,int ex,int y)
    {判断菱形内部是否都是'.'(3.3步)。
        int mid=(ex-sx)/2+sx;
        int l,r,x;//左边界、右边界和行数。
        for (l=y,r=y,x=sx+1;x<mid;l--,r++,x++)
            for (int j=l;j<=r;j++)
                if (s[x][j]=='#')
                    return false;
        //判断菱形上半部分内部是否都是'.'。
        for (;x<ex;l++,r--,x++)
            for (int j=l;j<=r;j++)
                if (s[x][j]=='#')
                    return false;
        //判断菱形内部下半部分是否都是'.'。
        return true;//如果条件都符合,那条件就成立。
    }
    int main()
    {//总控区。
        //输入数据(第一步)。
        cin>>n>>m;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                cin>>s[i][j];
            }
        }
        //遍历输入的数据(第二步)。
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                if (s[i][j]=='#')
                {//如果是'#',那么说明有可能是顶点。
    
                    //判断大小(3.1步)。
                    int da=sou(i,j);//搜索最下面的点。
                    if (da==i+1 || (da-i)%2==1)
                    {//如果这两个点不能组成菱形。
                        continue;//直接判断下一个。
                    }
                    if (da==n+1)
                    {//没找到底端'#',不是合格的钻石。
                        continue;
                    }
    
                    //判断边界是否都是'#'(3.2步)。
                    z1=panbian(i,da,j);//判断菱形四条边上是否都是'#'。
                    if (!z1)
                    {//不符合条件。
                        continue;
                    }
    
                    //判断内部是否都是'.'(3.3步)。
                    z2=pannei(i,da,j);//判断菱形内部是否都是'.'。
                    if (!z2)
                    {//如果条件不成立。
                        continue;
                    }
                    cnt++;//如果前面都通过了,那么他就是一个合格的钻石(菱形)。所以:
                    //计数器加一。
                }
            }
        }
        cout<<cnt;//输出计数器的值。
        return 0;
    }
    
    • 3
      @ 2022-7-26 22:16:33

      想起来这道题就把题解补一下 用了几个定理

      正方形对角线垂直且相等
      正方形对角线交点到四个边顶点距离相等
      

      这题看输入像是菱形,其实你看每条边长度相等,对角线长度也相等就是显示不出来,我们可以把它当做斜放的正方形来看待

      接下来就是分析题目

      内部均匀意味着里面全是由.构成的没有其他杂质
      边一定完整
      

      然后就是编写环节

      任意找到一个'.'那么如果这个点到四周最近的#距离相等,那么这个点一定是一个不确定钻石的中心点

      为了优化,我们可以分析出一下几点

      1.这个点一定不在输入的边缘,不然这个点至少有一个方向是一定没有其他字符的
      2.这个点如果满足上述情况,那么一定可以解决如果有钻石在一个钻石内部且一条边与大钻石边平行的套娃问题
      3.代码太长,底部直接放完整代码
      

      在上面的基础上,我们还应该判断一条边是否完整

      那么如果这个中心点和中心点到顶点的距离已经确定,那么每行#之间的距离也就已经确定,我们只需要根据这两个值确定关系即可
      放代码太长了,这部分直接在底部放完整代码
      

      接下来判断里面是否有小钻石套娃

      已知正方形对角线交点位置和对角线一半长,那么就能推出每行的.应该有几个,这样只需要判断这些.里面是否混入内奸#即可
      还是放代码还是太长了,底部完整代码再看
      

      然后就没有其他情况了,如果上述条件均成立,那么这就是一颗完整无瑕疵的钻石!恭喜(

      完整代码

      #include<bits/stdc++.h>
      using namespace std;
      int n , m , ans ;
      char a[ 2001 ][ 2001 ] ;
      int main()
      {
          ios::sync_with_stdio( 0 ) ;
          cin.tie( 0 ) ;
          cin >> n >> m ;
          for( int i = 1 ; i <= n ; i ++ )
          {
              for( int ia = 1 ; ia <= m ; ia ++ )
              {
                  cin >> a[ i ][ ia ] ;
              }
          }
          for( int i = 2 ; i <= n - 1 ; i ++ )
          {
              for( int ia = 2 ; ia <= m - 1 ; ia ++ )
              {
                  if( a[ i ][ ia ] == '.' )
                  {
                      //判断顶点距离
                      int tes1 = -1 , tes2 = -1 , tes3 = -1 , tes4 = -1 ;
                      for( int iaa = i - 1 ; iaa >= 1 ; iaa -- )
                      {
                          if( a[ iaa ][ ia ] == '#' ) 
                          {
                              tes1 = i - iaa ; 
                              break ;
                          }
                      }
                      for( int iab = i + 1 ; iab <= n ; iab ++ )
                      {
                          if( a[ iab ][ ia ] == '#' ) 
                          {
                              tes2 = iab - i ;
                              break ;
                          }
                      }
                      for( int iac = ia - 1 ; iac >= 1 ; iac -- )
                      {
                          if( a[ i ][ iac ] == '#' )
                          {
                              tes3 = ia - iac ;
                              break ;
                          }
                      }
                      for( int iad = ia + 1 ; iad <= m ; iad ++ )
                      {
                          if( a[ i ][ iad ] == '#' )
                          {
                              tes4 = iad - ia ;
                              break ;
                          }
                      }
                      if( tes1 == tes2 and tes2 == tes3 and tes3 == tes4 and tes1 != -1 )
                      {
                          //判断边是否完整
                          int tes5 = 0 ;
                          bool abl = 1 ;
                          for( int iaaa = i - tes1 ; iaaa <= i + tes1 ; iaaa ++ )
                          {
                              if( a[ iaaa ][ ia + tes5 ] != '#' or a[ iaaa ][ ia - tes5 ] != '#' )
                              {
                                  abl = 0 ;
                                  break ;
                              }
                              if( iaaa < i ) tes5 ++ ;
                              else tes5 -- ;
                          }
                          if( abl )
                          {
                              bool abl2 = 1 ;
                              int tes6 = 0 ;
                              for( int iaaaa = i - tes1 + 1 ; iaaaa <= i + tes1 - 1 ; iaaaa ++ )
                              {
                                  for( int iaaaaa = ia - tes6 ; iaaaaa <= ia + tes6 ; iaaaaa ++ )
                                  {
                                      //判断里面是否没有#(也就是是否有套娃)
                                      if( a[ iaaaa ][ iaaaaa ] != '.' )
                                      {
                                          abl2 = 0 ;
                                          break ;
                                      }
                                  }
                                  if( iaaaa < i ) tes6 ++ ;
                                  else tes6 -- ;
                              }
                              if( abl2 ) ans ++ ;
                          }
                      }
                  }
              }
          }
          cout << ans ;
          return 0;
      }
      
      • 1
        @ 2023-8-7 17:06:38

        思路: 枚举每一个点,找到可能的以这一点为中心的菱形,判断是否成立

        是不是有点暴力? image 其实楼下的都一样

        #include <bits/stdc++.h>
        using namespace std;
        int n, m, ans;
        char mp[2005][2005];
        int main()
        {
            ios::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            cin >> n >> m;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    cin >> mp[i][j];
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    if (mp[i][j] == '.')
                    {
                        int s=i, x=i, z=j, y=j;
                        bool flag = 1;
                        while (s>=1&&mp[s][j] == '.') s--;//上端点
                        while (x<=n&&mp[x][j] == '.') x++;//下端点
                        while (z>=1&&mp[i][z] == '.') z--;//左端点
                        while (y<=m&&mp[i][y] == '.') y++;//右端点
                        if (s == 0 || x == n+1 || z == 0 || y == m+1) continue;
                        if (i-s!=x-i || i-s!=j-z || i-s!=y-j || x-i!=j-z || x-i!=y-j || j-z!=y-j) continue;
                        for (int k = s; flag && k <= i; k++)
                            for (int l = s+j-k; flag && l <= j+k-s; l++)
                            {
                                if ((l == s+j-k || l == j+k-s) && mp[k][l] == '.') flag = 0;//判断边
                                if ((l != s+j-k && l != j+k-s) && mp[k][l] == '#') flag = 0;//判断内部
                            }//判断上面一半三角形
                        for (int k = i+1; flag && k <= x; k++)
                            for (int l = z-i+k; flag && l <= y+i-k; l++)
                            {
                                if ((l == z-i+k || l == y+i-k) && mp[k][l] == '.') flag = 0;//判断边
                                if ((l != z-i+k && l != y+i-k) && mp[k][l] == '#') flag = 0;//判断内部
                            }//判断下面一半三角形
                        if (flag)
                            ans++;
                    }
            cout << ans;
            return 0;
        }
        
        • -1
          @ 2023-8-11 18:06:54
          using namespace std;
          int n, m, ans;
          char mp[2005][2005];
          int main()
          {
              ios::sync_with_stdio(0);
              cin.tie(0);
              cout.tie(0);
              cin >> n >> m;
              for (int i = 1; i <= n; i++)
                  for (int j = 1; j <= m; j++)
                      cin >> mp[i][j];
              for (int i = 1; i <= n; i++)
                  for (int j = 1; j <= m; j++)
                      if (mp[i][j] == '.')
                      {
                          int s=i, x=i, z=j, y=j;
                          bool flag = 1;
                          while (s>=1&&mp[s][j] == '.') s--;//上端点
                          while (x<=n&&mp[x][j] == '.') x++;//下端点
                          while (z>=1&&mp[i][z] == '.') z--;//左端点
                          while (y<=m&&mp[i][y] == '.') y++;//右端点
                          if (s == 0 || x == n+1 || z == 0 || y == m+1) continue;
                          if (i-s!=x-i || i-s!=j-z || i-s!=y-j || x-i!=j-z || x-i!=y-j || j-z!=y-j) continue;
                          for (int k = s; flag && k <= i; k++)
                              for (int l = s+j-k; flag && l <= j+k-s; l++)
                              {
                                  if ((l == s+j-k || l == j+k-s) && mp[k][l] == '.') flag = 0;//判断边
                                  if ((l != s+j-k && l != j+k-s) && mp[k][l] == '#') flag = 0;//判断内部
                              }//判断上面一半三角形
                          for (int k = i+1; flag && k <= x; k++)
                              for (int l = z-i+k; flag && l <= y+i-k; l++)
                              {
                                  if ((l == z-i+k || l == y+i-k) && mp[k][l] == '.') flag = 0;//判断边
                                  if ((l != z-i+k && l != y+i-k) && mp[k][l] == '#') flag = 0;//判断内部
                              }//判断下面一半三角形
                          if (flag)
                              ans++;
                      }
              cout << ans;
              return 0;
          }
          
          
          • 1

          信息

          ID
          1915
          时间
          1000ms
          内存
          256MiB
          难度
          4
          标签
          (无)
          递交数
          109
          已通过
          51
          上传者