安贞网站建设,铜山区建设局招投标网站,做运动特卖的网站,品牌形象设计案例网站题目#xff1a;
小明有一张N*M的方格纸#xff0c;且部分小方格中涂了颜色#xff0c;部分小方格还是空白。 给出N (2Ns30)和M(2sMs30)的值#xff0c;及每个小方格的状态(#xff08;被涂了颜色小方格用数字1表示#xff0c;空白小方格用数字0表示)#xff1b; 请…题目
小明有一张N*M的方格纸且部分小方格中涂了颜色部分小方格还是空白。 给出N (2Ns30)和M(2sMs30)的值及每个小方格的状态(被涂了颜色小方格用数字1表示空白小方格用数字0表示) 请帮助小明找出最大的矩形空白区域,并输出该矩形空白区域由多少个小方格组成。 例如:N4, M54*5的方格纸中每个小方格的状态如下图: 最大的空日区域由6个小方格组成(红色框区域)。 思路
暴力穷举法
1、将每一个方格的下边0的个数、右边0的个数进行统计
2、在由下边0的个数和右边0的个数以及该方格围城的矩形中筛选出值是1的方格进行0个数的回退。
3、将每一个方格的下标、下边0的个数右边0的个数进行保存最后再求最大的面积
4、如果这个方格里面是1则从该方格出发是不能构成数据全部为0的矩形的行刺可以直接将该方格的下边0和右边0的个数设置为0排除即可。
5、最后查找 下边0的个数 1 同时 右边0的个数也 1的找到面积最大的矩形。 代码
#includestdio.h
#define N 4
#define M 5
#define NUM (N*M)int main()
{int arr[N][M] {{1,1,0,0,0},{1,0,1,0,0},{0,0,0,1,1},{0,0,0,1,0},};// 本例采用数组存储因为有多个数组因此采用 二维数组方式int posArr[NUM][4]{0};// 先获取每一个数据// arr数据的行下标 int i;// arr数据的列下标 int j;printf(原始数组信息\n);for(i0;iN;i){for(j0;jM;j){printf(%d ,arr[i][j]); }printf(\n);}// 查找下边0的临时下标 int k;// 查找右边0的临时下标 int t;// 下边0的个数 int bottom 0;// 右边0的个数 int right 0;// 存放最大矩形信息的下标。int maxI;// 最大矩形的面积 int maxArea;for(i0;iN;i){for(j0;jM;j){ // 如果该数据是1不能构成以这个点为定点的矩形则不需要向下和向右统计0的个数了 if(arr[i][j] ! 0){posArr[i*Mj][0] i; posArr[i*Mj][1] j; posArr[i*Mj][2] 0; posArr[i*Mj][3] 0; continue;}// 如果该数据是0,可能构成 以这个点为定点的矩形bottom 0;right 0;// 查找下边0的个数for(kj1;kM;k){if(arr[i][k] 0){right;}else{break;}} // 向右查找0的个数for(ti1;tN;t){if(arr[t][j] 0){bottom;}else{break;}} // 以行为准查找1将不和要求的矩形排除掉当前位置为i 和 j for(ki1;ki bottom;k){for(tj;tj right;t){if(arr[k][t] 1){if(k t){bottom - 1;}else if(k t){right - 1;}else{bottom - 1;right - 1;}}}} posArr[i*Mj][0] i; posArr[i*Mj][1] j; posArr[i*Mj][2] bottom; posArr[i*Mj][3] right; } } // 访问数据maxI 0;maxArea0; int tempArea 0;for(i0;iNUM;i){if(posArr[i][2] 0 posArr[i][3] ! 0){tempArea 1 * posArr[i][3];}if(posArr[i][2] ! 0 posArr[i][3] 0){tempArea 1 * posArr[i][2];}if(posArr[i][2] 0 posArr[i][3] 0){tempArea 1;}if(posArr[i][2] ! 0 posArr[i][3] ! 0){tempArea (posArr[i][2]1) * (posArr[i][3]1);}if(maxArea tempArea){maxI i;maxArea tempArea;} } printf(最大矩形的信息:\n);printf(左上角的坐标点为第%d行第%d列\n,posArr[maxI][0],posArr[maxI][1]);printf(宽%d,高%d\n,posArr[maxI][3]1,posArr[maxI][2]1);printf(面积为:%d\n,(posArr[maxI][3]1)*(posArr[maxI][2]1));return 0;
}效果演示 拓展
求正方形该代码也使用查找 下方0个数和右边0个数一样的组合即可。
