1209 最大面积

╰半夏微凉° 2022-05-15 04:15 188阅读 0赞

1209: 最大面积

给定一个n\*m的矩阵，其中有k个格子是1，其他全部是0。  
你的任务是告诉我最大的全部由1组成的图形的最大面积为多少？  
Input

输入包括多组测试数据，第一行为三个正整数n,m,k，(1<=n,m<=100,1<=k<=n\*m)，接下来k行，每行有两个正整数x,y(1<=x<=n,1<=y<=m)代表格子(x,y)是1。

Output

对于每组测试数据，输出最大的面积。

Sample Input

3 4 5  
3 2  
2 2  
3 1  
2 3  
1 1  
Sample Output  
【分析】  
由于最近才看的回溯法，所以运用的不是很纯熟，一开始做这道题是用走迷宫的思想做的，但这样就考虑的有点多，就一直时间超限，后来看到大神的代码启发，简化了一下；就ac了；

【代码】

#include<stdio.h>
    #include<string.h>
    #define max(a,b) (a>b?a:b)
    int map[1001][1001];
    int dx[4]={ 1,-1,0,0},dy[4]={ 0,0,-1,1},num;
    void dfs(int x,int y){ 
        int i;
        map[x][y]=0;
    	for(i=0;i<4;i++){ 
    		int a=x+dx[i];
    		int b=y+dy[i];
            if(map[a][b]==1) { 
                num++;
                dfs(a,b);
            }
    	}
    }
    int main()
    { 
        int n,m,k;
    	while(~scanf("%d%d%d",&n,&m,&k))
    	{ 
    	    num=0;
    		memset(map,0,sizeof(map));
    		int i,j,x,y,maxx=0;
    		for(i=0;i<k;i++)
            { 
                scanf("%d%d",&x,&y);
                map[x-1][y-1]=1;
            }
            for(i=0;i<n;i++)
                for(j=0;j<m;j++)
                { 
                    num=1;
                    if(map[i][j]==1){ 
                        dfs(i,j);
                        maxx=max(num,maxx);}
                    }
            printf("%d\n",maxx);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，188人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-最大的正方形面积

题目表述 Given a 2D binary matrix filled with 0’s and 1’s, find the largest square cont...

朴灿烈づ我的快乐病毒、/ 2024年04月18日 23:46/ 0 赞/ 63 阅读

相关 695. 岛屿的最大面积

695. 岛屿的最大面积给你一个大小为 m x n 的二进制矩阵 grid 。岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在

古城微笑少年丶/ 2024年03月31日 08:50/ 0 赞/ 58 阅读

相关 leetcode695. 岛屿的最大面积

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】][offer_

Love The Way You Lie/ 2024年03月26日 10:39/ 0 赞/ 56 阅读

相关 695. 岛屿的最大面积

> 给定一个包含了一些 0 和 1 的非空二维数组 grid 。 > > 一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者

灰太狼/ 2022年10月08日 05:44/ 0 赞/ 139 阅读

相关 Leetcode 695. 岛屿的最大面积

题目重述给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平

青旅半醒/ 2022年09月08日 12:55/ 0 赞/ 175 阅读

相关求柱状图最大面积

> 给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的宽度都为1。在这组柱状图中找到能组成的最大矩形的面积（如图所示）。入参h为一个整型数组，代表每个柱子的

浅浅的花香味﹌/ 2022年06月07日 00:43/ 0 赞/ 222 阅读

相关 1209 最大面积

1209: 最大面积给定一个n\m的矩阵，其中有k个格子是1，其他全部是0。你的任务是告诉我最大的全部由1组成的图形的最大面积为多少？ Input 输入包括多组

╰半夏微凉°/ 2022年05月15日 04:15/ 0 赞/ 188 阅读

相关 leetcode 812. 最大三角形面积

近期一直在用python刷leetcode的题，代码都提交到了github上了：[https://github.com/Teingi/test][https_github.co

短命女/ 2022年04月17日 04:06/ 0 赞/ 186 阅读

相关岛屿的最大面积

1、题目描述给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的

àì夳堔傛蜴生んèń/ 2022年01月21日 08:51/ 0 赞/ 205 阅读

相关 695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着

迷南。/ 2021年11月14日 13:08/ 0 赞/ 314 阅读