(一一〇)二维数组里找零最多的题目

  1. 云栖社区>
  2. 博客>
  3. 正文

(一一〇)二维数组里找零最多的题目

零零水 2016-01-13 23:22:00 浏览908
展开阅读全文

题目 - 最大零矩阵(附加题)

描述

有一个二位数组 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;

}

总结:

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


网友评论

登录后评论
0/500
评论
零零水
+ 关注