题目的内容在这里：#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;}
