uva 201 Squares

A children’s board game consists of a square array of dots that contains lines connecting some of the pairs of adjacent dots. One part of the game requires that the players count the number of squares of certain sizes that are formed by these lines. For example, in the figure shown below, there are 3 squares — 2 of size 1 and 1 of size 2. (The “size” of a square is the number of lines segments required to form a side.)

Your problem is to write a program that automates the process of counting all the possible squares.

Input
The input file represents a series of game boards. Each board consists of a description of a square array
of n 2 dots (where 2 ≤ n ≤ 9) and some interconnecting horizontal and vertical lines. A record for a
single board with n 2 dots and m interconnecting lines is formatted as follows:

Line 1: n the number of dots in a single row or column of the array
Line 2: m the number of interconnecting lines
Each of the next m lines are of one of two types:

H i j indicates a horizontal line in row i which connects the dot in column j to the one to its right in column j + 1
or
V i j indicates a vertical line in column i which connects the dot in row j to the one below in row j + 1

Information for each line begins in column 1. The end of input is indicated by end-of-file. The first
record of the sample input below represents the board of the square above.
Output
For each record, label the corresponding output with ‘Problem #1’, ‘Problem #2’, and so forth. Output
for a record consists of the number of squares of each size on the board, from the smallest to the largest.
lf no squares of any size exist, your program should print an appropriate message indicating so. Separate
output for successive input records by a line of asterisks between two blank lines, like in the sample
below.
Sample Input

4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
Sample Output

Problem #1

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #2

No completed squares can be found.

中文：

给你一个二个二位点阵，给你一个格式，表示两点之间连了一条线，H i,j 表示 第i行第j列的点，水平方向与第i行第j+1列的点连了一条线
V i,j 表示第i列第j行的点，与水平方向第i列第j+1行的点连了一条直线。

问你这个点阵有多少个正方形，输出不同尺寸正方形的个数

#include<iostream>
#include <string>
#include <algorithm>
#include <strstream>
#include <cmath>
#include <map>
#include <vector>
#include <cstring>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

map<PII, PII> H;
map<PII, PII> V;
int n, m ,t=0,flag;



int ans[10];

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n >> m)
    {
        memset(ans, 0, sizeof(ans));
        PII ter = make_pair(-1, -1);
        int x, y;
        char c;
        H.clear();
        V.clear();
        for (int i = 1; i <= m; i++)
        {
            cin >> c >> x >> y;
            if (c == 'H')
            {
                H[make_pair(x, y)] = make_pair(x, y + 1);
            }
            else
            {
                V[make_pair(y, x)] = make_pair(y+1, x);
            }

        }
        //cout << V[make_pair(1, 2)].first << " " << V[make_pair(1,2)].second << endl;

        for (int len = 1; len <= n - 1; len++)
        {
            int cnt ;
            for (int row = 1; row <= n; row++)
            {
                for (int col = 1; col <= n; col++)
                {
                    cnt = 0;
                    flag = 0;
                    PII p = make_pair(row, col);
                    while (H.find(p) != H.end())
                    {
                        p = H[p];
                        if (p == ter)
                            break;
                        cnt++;
                        if (cnt == len)
                        {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag)
                        continue;

                    flag = 0;
                    cnt = 0;
                    p = make_pair(row + len , col);
                    while (H.find(p) != H.end())
                    {
                        p = H[p];
                        if (p == ter)
                            break;
                        cnt++;
                        if (cnt == len)
                        {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag)
                        continue;

                    flag = 0;
                    cnt = 0;
                    p = make_pair(row, col);
                    while (V.find(p) != V.end())
                    {
                        p = V[p];
                        if (p == ter)
                            break;
                        cnt++;
                        if (cnt == len)
                        {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag)
                        continue;

                    flag = 0;
                    cnt = 0;
                    p = make_pair(row, col + len);
                    while (V.find(p) != V.end())
                    {
                        p = V[p];
                        if (p == ter)
                            break;
                        cnt++;
                        if (cnt == len)
                        {
                            flag = 1;
                            break;
                        }
                    }

                    if (!flag)
                        continue;

                    ans[len]++;
                }
            }
        }

        if (t!=0)
        {
            cout << endl;
            cout << "**********************************" << endl << endl;
        }

        cout << "Problem #" << ++t << endl << endl;
        flag = 0;
        for (int i = 1; i <=n; i++)
        {
            if (ans[i] != 0)
            {
                flag = 1;
                cout << ans[i] << " square (s) of size " << i << endl;
            }
        }

        if (!flag)
        {
            cout << "No completed squares can be found." << endl;
        }


    }
    return 0;
}

解答：

注意纵向输入的行和列是反过来的，用一个map保存当前点所连接的下一个点，枚举正方形边长即可