1 条题解

  • 0
    @ 2025-4-6 21:35:07

    题目描述

    儿童棋盘游戏由一个方形的点数组组成,其中包含连接一些点的线条。游戏的一部分要求玩家计算这些线形成的正方形数。例如,在下图中,有3个平方,2个大小为1,大小为2,因此平方总数为3。(正方形的“大小”是形成侧面所需的线段数。

    你的任务是写一个程序来计算所有可能的正方形的数量。 输入

    输入代表一系列游戏板。每个板由一个平方数组的n ^ 2个点(其中2 <= n <= 1500)和一些相互连接的水平和垂直线组成。具有n ^ 2个点和m(m <=30000)互连行的单个板的记录如下:

    第1行:“n”单行或列中的点数。

    第2行:“m”互连线路数。

    下一个 m 行是以下两种类型之一:

    “H i j k”(1 <= i,j <= n,k >0,j + k <= n)表示从行i中的点的水平长度k,列j到行i中的点,列j到行i中的点,列j。

    “V i j k”(1 <= i,j <= n,k >0,i + k <= n)表示长度k的垂直行,从行i,列j到行i + k,列j到行中的点。

    输入的结束用文件结尾表示。

    输出:

    对于每个记录,打印只有一个整数,即平方数。 输入数 1

    #include <algorithm>
    #include <iostream>
    #include <queue>
    #include <cmath>
    #include <set>
    #include <vector>
    #include <string>
    #include <sstream>
    #include <ctype.h>
    #include <string.h>
    using namespace std;
     
    const int N = 10;
    const int INF = 1000000;
     
    int hor[N][N];
    int ver[N][N];
     
    int main()
    {
      //  freopen("in.txt", "r", stdin);
        int T = 0, dot, edge, x, y, ans[15], Case = 1;
        char c[5];
        while(~scanf("%d%d", &dot, &edge))
        {
            memset(hor, 0, sizeof(hor));
            memset(ver, 0, sizeof(ver));
            memset(ans, 0, sizeof(ans));
            while(edge --)
            {
                cin >> c;
                scanf("%d%d", &x, &y);
                if(c[0] == 'H') hor[x][y] = 1;
                else if(c[0] == 'V') ver[y][x] = 1;
            }
            int sta = dot - 1;//标准化
            if(T ++) printf("\n**********************************\n\n");
      /*      for(int i = 1; i <= dot; i ++)
            {
                for(int j = 1; j <= sta; j ++)
                    printf("%d ", hor[i][j]);
                printf("\n");
            }
            for(int i = 1; i <= sta; i ++)
            {
                for(int j = 1; j <= dot; j ++)
                    printf("%d ", ver[i][j]);
                printf("\n");
            }*/
            for(int i = 1; i <= sta; i ++) //边长度的延伸
            {
                for(int j = 1; j + i <= dot; j ++)//判断行
                {
                    for(int k = 1; k + i <= dot; k ++)//判断列
                    {
                        int flag = 1;
                        for(int l = 0; l <= i; l += i)
                            for(int m = 0; m <= i - 1; m ++)
                            {
                                if(hor[j + l][k + m] == 0)
                                {
                                    flag = 0;
                             //       printf("fuck1");
                              //      printf("fuck1---<%d, %d>\n", j + l, k + m);
                                    break;
                                }
                            }
                        for(int l = 0; l <= i - 1; l ++)
                            for(int m = 0; m <= i; m += i)
                            {
                                if(ver[j + l][k + m] == 0)
                                {
                                    flag = 0;
                              //      printf("fuck2---<%d, %d>\n", j + l, k + m);
                                    break;
                                }
                            }
                        if(flag == 1) { ans[i] ++;/* printf("可行解:<%d, %d>\n", j, k); */}
                    }
                }
            }
            printf("Problem #%d\n\n", Case ++);
            int flag1 = 0;
            for(int i = 1; i <= sta; i ++)
            {
                if(ans[i])
                {
                    printf("%d square (s) of size %d\n", ans[i], i);
                    flag1 = 1;
                }
            }
            if(!flag1) printf("No completed squares can be found.\n");
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1446
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    0
    上传者