ACM UVa 算法题 #201 - Squares解法

题目的内容在这里：#201 - Squares

解法我所能想到的有两种，先说慢一些的：

1. 较慢的算法，复杂度O(N^4)

我一开始想到的算法如下：对于每个点，可以从该点出发，把该点看成矩形的左上角，检查是否存在大小从1到N的矩形（当然不可以超过边界），检查是否存在这样的矩形每一次需要花上O(n)的时间（检查四条边，可以优化一些，但是复杂度必为O(n)），因此总的复杂度是O(N^4)

2. 快一些的算法，复杂度O(N^3)

后来，我觉得还有一定的改进余地，便继续思考了一阵子，最后发现有办法可以加快检查矩形的速度，达到线性复杂度。假设我们检查左上角为(x,y)大小为size的矩形是否存在，最直接的方法自然是直接遍历每条水平线和垂直线，所需时间为O(n)。如果我们已知矩形的四个顶点是否连接，那么直接检查这个四个顶点连接关系便可以直接得出结果。

初步的想法是构造一个邻接矩阵，记录每两点是否直接连通（不考虑不在同一条直线上的两点）。但是在此题中其实并不需要构造邻接矩阵，我们已经有right_adj和down_adj记录某点(x,y)是否和右边的邻接点和下面的邻接点相连，我们可以扩展这个数据结构，记录某个点(x, y)到最右边的连通的点的距离和最下面的连通的点的距离。比如(1,1)->(2, 1)->(3, 1) (4, 1)->(5, 1)那么right_adj[1][1] = 2, right_adj[2][1] = 1, right_adj[3][1] = 0, right[4][1] = 1。这样，检查矩形只需用查此数据结构4次，检查四条边即可，具体可以参看下面代码中的Is_square方法。

那么如何计算right_adj和down_adj呢？其实这个过程是比较简单的，以计算right_adj为例，对于每一行，从右往左连续检查每两点之间是否连通，如果连通则继续处理，记录连通的直线的start和end，然后计算right_adj=end - start。如果发现不连通则把当前点作为新的start，然后继续从右往左检查，直到检查完整行为止。这个计算是两重循环，复杂度为O(n)。具体可以参看main中"try to calculate right_adj / down_adj"的部分。

这样，最后复杂度总的为O(n^3)，比之前的算法速度提升了一个数量级。

最后附上代码：

// 
// ACM UVa Problem #201
// http://acm.uva.es/p/v2/201.html
//
// Author:  ATField
// Email:   atfield_zhang@hotmail.com
//

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <algorithm>

using namespace std;

#define MAX 10

int right_adj[MAX][MAX];            // (x, y) horizontally connected to (x + right_adj[MAX][MAX], y)
int down_adj[MAX][MAX];             // (x, y) vertically connected to (x, y + down_adj[MAX][MAX] )

int squares[MAX];                   // squares of size i, 0 not used

int n;

//
// constant check for square (left, top) = (x, y) of size len
//
bool is_square(int x, int y, int len)
...{
    // check top edge, right_adj[x][y] >= len means that the horizontal line from (x, y) is the same as or longer than len
    if( right_adj[x][y] < len )
        return false;

    // check right edge
    if( down_adj[x][y] < len )
        return false;

    // check left edge
    if( down_adj[x + len][y] < len )
        return false;

    // check bottom edge
    if( right_adj[x][y + len] < len)
        return false;

    return true;
}

int main(int argc, char *argv[])
...{
    int problem_id = 0;

    while(1)
    ...{
        problem_id ++;

        memset(right_adj, 0, sizeof(right_adj));
        memset(down_adj, 0, sizeof(down_adj));
        memset(squares, 0, sizeof(squares));

        int num_lines;

        cin >> n;               // n * n 
        if( cin.eof() )
            break;

        cin >> num_lines;       

        //
        // read in data  
        // initially right_adj & down_adj only = 0 or 1
        //
        for( int i = 0; i < num_lines; ++i )
        ...{
            char line_type;
            cin >> line_type;

            if( line_type == 'H' )
            ...{
                int x, y;
                cin >> y >> x;

                right_adj[x - 1][y - 1] = 1;
            }
            else
            ...{
                int x, y;
                cin >> x >> y;

                down_adj[x - 1][y - 1] = 1;
            }
            
        }

        //
        // try to calculate maximum right_adj
        //
        for( int y = n - 1; y >= 0; y-- )
        ...{
            int end = n - 1;
            int start = end - 1;
            while( start >= 0 )
            ...{
                if( right_adj[start][y] )
                ...{
                    right_adj[start][y] = end - start;
                    start --;
                }
                else
                ...{
                    end = start;
                    start--;
                }
            }
        }

        // try to calculate maximum down_adj
        for( int x = n - 1; x >= 0; x -- )
        ...{
            int end = n - 1;
            int start = end - 1;
            
            while( start >= 0 )
            ...{
                if( down_adj[x][start] )
                ...{
                    down_adj[x][start] = end - start;
                    start --;
                }
                else
                ...{
                    end = start;
                    start--;
                }
            }
        }

        //
        // check every location O(n*n) for squares size 1~n O(n)
        // because of calculation above, is_square(x, y, len) only requires constant time
        // O(3)!
        //
        for( int y = 0; y < n - 1; y++ )
        ...{
            for( int x = 0; x < n - 1; x++ )
            ...{
                if( !(right_adj[x][y] && down_adj[x][y]) )
                    continue;

                int max_len = min(n - x - 1, n - y - 1);
                max_len = min(max_len, right_adj[x][y]);
                max_len = min(max_len, down_adj[x][y]);

                for( int len = 1; len <= max_len; len++ )
                ...{
                    if( is_square(x, y, len) )
                        squares[len]++;
                }
            }
        }

        cout << endl << "**********************************" << endl << endl;

        cout << "Problem #" << problem_id << endl << endl;

        bool has_square = false;
        for( int i = 1; i < n; ++i )
            if( squares[i] )
            ...{
                cout << squares[i] << " square (s) of size " << i << endl;
                has_square = true;
            }

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

    return 0;
}