网易互娱第四题：求矩形字符数组内最大相等正方形

作者：日新

	//过了62%，后面交卷后考虑应该是顶点坐标位置出了问题；



	//思路就是先两重for循环依次确定一个正方形的起点，再两重for循环确定另一个正方形的起点（可以是第一个顶点的正上、正左，和右方）



	//find函数查看是否是相等正方形，先根据顶点求出可能存在的最大正方形边长，然后一次比较，其实就是比较新添加正方形的外围一圈，相当于最右边一列，最下面一行

#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<set>
#include<algorithm>
#include<functional>
#include<math.h>
using namespace std;
int xx1, xx2;
int yy1, yy2;
int maxv=0;
int num, len;
vector<string> cun;
void find(int x1, int y1, int x2, int y2)
{
	int cmax = 1;
	int tmp = min(num - x2, len - y2);
	for (int i = 1; i < tmp; i++)
	{
		int cx1 = x1 + i;
		int cy1 = y1 + i;
		int cx2 = x2 + i;
		int cy2 = y2 + i;
		int k1 = x1;
		int k2 = x2;
		int num = i;
		while (cun[k1++][cy1] == cun[k2++][cy2] &&(num--)>0);
		if (num!=-1)
			break;

		int g1 = y1;
		int g2 = y2;
		num = i;
		while (cun[cx1][g1++] == cun[cx2][g2++] && (num--)>0);
		if (num != -1)
			break;
		cmax++;
	}
	if (cmax > maxv)
	{
		maxv = cmax;
		xx1 = x1;
		xx2 = x2;
		yy1 = y1;
		yy2 = y2;
	}

};
int main()
{	
	cin >> num >> len;
	string tmp;
	int k = num;
	while (k-- > 0)
	{
		cin >> tmp;
		cun.push_back(tmp);
	}
	for (int i = 0; i < num; i++)
		for (int j = 0; j < len; j++)
		{
			for (int k = 0; k < num; k++)
				for (int g = 0; g < len; g++)
				{
					if (k < i && g < j || k==i && g==j)
						continue;
					if (cun[i][j] == cun[k][g])
						find( i,  j,  k,  g);
				}
		}

	cout << maxv << endl;

	cout << xx1+1 << ' ' << yy1+1 << endl;
	cout << xx2+1 << ' ' << yy2+1 << endl;


	system("pause");
	return 0;

}