（一一〇）二维数组里找零最多的题目

题目 - 最大零矩阵（附加题）

描述

有一个二位数组 m（<100）行, n（<100） 列，其元素为不大于100的非负整数。现要找元素值均为0的最大子二维数组，其中行相邻，列也相邻，行数与列数之积最大(即，所含0元素最多)，输出该最大积。例如：

2 5 0 0 8 11 15

3 0 0 0 0 12 16

7 0 0 0 0 13 17

8 0 0 7 1 14 18

4 0 0 0 0 0 0

6 0 0 0 0 0 0

这是6行，7列构成的二维数组，其中：由第4~5行(最后2行)，第1~6列（最后6列）构成的子数组最大，共有12个0元素，因此，应该输出 12。其它情况下的子数组都不多于12个0元素，例如，第1~5行与第1~2列构成子数组为第二大数组，含有10个0元素。

关于输入

第一行，m 和 n 的值，以空格间隔，m 和 n 均为 不大于 100 的正整数 之后，共 m 行，每行共 n 个元素，其间用空格间格。

关于输出

输出，最大零元素子二维数组所含的 0 元素个数，如果没有0元素，则输出0。

例子输入

6 7

2 5 0 0 8 11 15

3 0 0 0 0 12 16

7 0 0 0 0 13 17

8 0 0 7 1 14 18

4 0 0 0 0 0 0

6 0 0 0 0 0 0

例子输出

12

#include<iostream>
#include<fstream>


using namespace std;


int main()
{
	int m;
	int n;
	ifstream file;
	file.open("abc.txt");
	file >> m;
	file >> n;
	unsigned short **pa = new unsigned short*[n];//new一个指针，指向有n个元素指针数组
	for (int i = 0;i < m;i++)
		pa[i] = new unsigned short[n];//每次new一个有n个元素的short数组，并让x[i]指向他
									  //pa[m][n]为这个二维数组


	for (int i = 0;i < m;i++)//从文件读入二维数组
		for (int j = 0;j < n;j++)
			file >> pa[i][j];


	for (int i = 0;i < m;i++)//输出二维数组
	{
		for (int j = 0;j < n;j++)
		{
			cout << pa[i][j];
			cout << " ";
		}
		cout << endl;
	}


	int x = 0;//x,y为每次查找时的基准坐标
	int y = 0;
	int total_max = 0;//total_max为最多时的0数
	int total_1 = 0;//往右偏移0的个数
	int total_2 = 0;//往下偏移0的个数
	int total_3 = 1;
	int X, Y;//X,Y为用于记录变量的坐标


	for (x = 0;x < n;x++)
	{
		for (y = 0;y < m;y++)
		{
			total_1 = total_2 = 0;
			total_3 = 1;
			X = x, Y = y;//将基准值赋给X和Y
			if (pa[Y][X] != 0)continue;//如果这个坐标不为0，则没考虑的意义，进入下一次循环
			else if (X > 0 && Y>0)	//假如这个坐标，x-1的位置和y-1的位置都是0，那么他必然被下面的循环判定过。如果只有一个为0，可能这个坐标往一个方向还是有可能的（所以还存在再度优化可能）
			{
				if (pa[Y - 1][X] == 0 && pa[Y][X - 1] == 0)break;
			}

			while (X<n && (!pa[Y][X]))//往右数，不为0，且X小于n（横坐标最大值）
			{
				total_1++;
				X++;
			}//total_1为遇见非0数时的0的个数
			while (1)
			{
				total_2 = 0;
				Y++;//纵坐标+1
				if (Y == m)break;//如果Y坐标过界则结束循环
				X = x;//X归位
				while (X<n && total_2 < total_1 && (!pa[Y][X]))//首先，X在n范围之内，其次，X小于total
				{
					total_2++;
					X++;
				}
				if (total_2 == total_1)total_3++;//如果total_2==total_1，说明这行的0数量和上一行是相同的，于是跳到下一行
				else break;
			}
			int total_x = total_1*total_3;//先往右，再往下数，0最多的情况

			total_1 = total_2 = 0;
			total_3 = 1;
			X = x, Y = y;

			while (Y < m && (!pa[Y][X]))//往下数，不为0，且Y小于m（纵坐标最大行数）
			{
				total_1++;
				Y++;
			}//total_1为遇见非0数时的0的个数
			while (X<n)
			{
				total_2 = 0;
				X++;
				if (X == n)break;//如果X坐标过界则结束循环
				Y = y;
				while (Y<m && total_2 < total_1 && (!pa[Y][X]))
				{
					total_2++;
					Y++;
				}
				if (total_2 == total_1)total_3++;
				else break;
			}
			int total_y = total_1*total_3;//先往下，再往右数，0最多的情况


										  //如果得出的情况比total_max大，则赋值给他
			if (total_max < total_x)total_max = total_x;
			if (total_max < total_y)total_max = total_y;

		}
	}
	cout << total_max << endl;


	system("pause");
	return 0;

}

总结：

①之前一直纠结没出结果。原因在于，Y和X在偏移后，可能过界的问题。例如6x7的矩阵，X坐标如果是7，则已经在界外了。因此在偏移后，应该加入过界检测，如果过界，则停止这种行为。