UVa201 Squares(正方形)

思路：关键是怎么判断存在正方形，创建两个矩阵，一个是计算点(i, j)右边最多连着几个点；另外一个是计算点(i, j)下边最多连着几个点。然后比较就可以了。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int n, m;
int X[12][12], Y[12][12], Sq[12]; 

#define min(q,p) (q>=p?p:q)

void readPoint(){
	char a;
	int b, c, i;
	memset(X, 0, sizeof(X));
	memset(Y, 0, sizeof(Y));
	for(i = 0;i < m;i ++){
		cin>>a>>b>>c;
		if(a == 'H')Y[b][c] = 1;
		else X[c][b] = 1;
	}
}

void calXY(){
	int i, j, k;
	for(i = 1;i <= n;i ++){
		for(j = 1;j < n;j ++){
			for(k = j+1;k < n;k ++)
				if(Y[i][j] && Y[i][k])Y[i][j] ++;
				else break;
		} 
	}
	for(i = 1;i < n;i ++){
		for(j = 1;j <= n;j ++){
			for(k = i+1;k < n;k ++)
				if(X[i][j] && X[k][j])X[i][j] ++;
				else break;
		} 
	}
}

void calSq(){
	int i, j, k;
	memset(Sq, 0, sizeof(Sq));
	for(i = 1;i < n;i ++){
		for(j = 1;j < n;j ++){
			int s = min(Y[i][j], X[i][j]);
			for(k = 1;k <= s;k ++){
				if(min(Y[i+k][j], X[i][j+k]) >= k)Sq[k]++;
			}
		}
	}
}

int main(void){
	int Count = 0;
	while(cin>>n>>m){
		if(Count)printf("\n**********************************\n\n");
		readPoint();
	   	calXY();
	   	calSq();
	   	printf("Problem #%d\n\n", ++Count);
	   	int sum = 0;
	   	for(int i = 1;i < 11;i ++){
	   		sum += Sq[i];
	   		if(Sq[i])printf("%d square (s) of size %d\n", Sq[i], i);
		}
	   	if(!sum)printf("No completed squares can be found.\n");
	} 
    return 0;
}