3494 - 雨天

通过次数

提交次数

旧版界面

Time Limit : 1 秒 Memory Limit : 128 MB

小学生非常讨厌下雨天，特别是有水坑的情况下，由于害怕踩到水里，所以他希望你能帮他算出积水的面积和周长，我们把陆地抽象成为0,1矩阵，0表示陆地，1表示积水，我们把上下左右相连的积水认为是同一块积水，小学生希望算出最大的积水面积和周长。

<span style="font-family:宋体;font-size:16px;">如图</span><span></span>

<span style="font-size:16px;">0001</span>

<span style="font-size:16px;">0111</span>

<span style="font-size:16px;">0010</span>

<span style="font-size:16px;">0000</span>

<span style="font-family:宋体;font-size:16px;">最大积水面积为</span><span style="font-size:16px;">5</span><span style="font-family:宋体;font-size:16px;">，最大积水周长为</span><span style="font-size:16px;">12</span>

&nbsp;

<img alt="" src="http://tk.hustoj.com:80/attached/image/20141208/20141208161329_77574.jpg" />

&nbsp;

Input

测试包含多组测试数据

<span style="font-family:宋体;font-size:16px;">第一行输入</span><span style="font-size:16px;">2</span><span style="font-family:宋体;font-size:16px;">个整数</span><span style="font-size:16px;">n,m</span><span style="font-family:宋体;font-size:16px;">，用空格隔开</span><span></span>

<span><span style="font-size:16px;">1&lt;=n,m&lt;=1000</span><span style="font-size:16px;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span>

<span style="font-family:宋体;font-size:16px;">接下来</span><span style="font-size:16px;">n</span><span style="font-family:宋体;font-size:16px;">行，每行</span><span style="font-size:16px;">m</span><span style="font-family:宋体;font-size:16px;">个</span><span style="font-size:16px;">01</span><span style="font-family:宋体;font-size:16px;">字符</span><span></span>

Output

对于每组测试数据输出

<span style="font-family:宋体;font-size:16px;">最大积水面积和周长，中间用空格隔开</span><span></span>

<span style="font-family:宋体;"></span><span></span>&nbsp;

Examples

Input Format

Output Format

5 12

Solution C

#include<stdio.h>
#include<string.h>
int a[1005][1005],x,c;
int abc(int i,int j)
{
	x++;a[i][j]=2;
	if(a[i][j+1]==0)c++;
	if(a[i][j-1]==0)c++;
	if(a[i+1][j]==0)c++;
	if(a[i-1][j]==0)c++;
	if(a[i][j-1]==1)abc(i,j-1);
	if(a[i-1][j]==1)abc(i-1,j);
	if(a[i][j+1]==1)abc(i,j+1);
	if(a[i+1][j]==1)abc(i+1,j);
	return x;
}
int main()
{
	int n,m,i,j,t,max,mx;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
    	memset( a, 0, sizeof(a));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				scanf("%1d",&a[i][j]);
		c=x=max=t=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				if(a[i][j]==1){
					t=abc(i,j);
					if(t>max){max=t;mx=c;}
					c=0;x=0;}
			}
		printf("%d %d\n",max,mx);
	}
	return 0;
}

Solution C++

#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
int a[maxn][maxn];
int ans1,ans2;
int n,m;
void dfs(int x,int y)
{
    a[x][y]=2;
    if (x-1>=0){
        if (a[x-1][y]==1){
            ans1++;
            dfs(x-1,y);
        } else if (a[x-1][y]==0) ans2++;
    } else ans2++;
    if (x+1<n){
        if (a[x+1][y]==1){
            ans1++;
            dfs(x+1,y);
        } else if (a[x+1][y]==0) ans2++;
    } else ans2++;
    if (y-1>=0){
        if (a[x][y-1]==1){
            ans1++;
            dfs(x,y-1);
        } else if (a[x][y-1]==0) ans2++;
    } else ans2++;
    if (y+1<m){
        if (a[x][y+1]==1){
            ans1++;
            dfs(x,y+1);
        } else if (a[x][y+1]==0) ans2++;
    } else ans2++;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(a,0,sizeof(a));
        for (int i=0;i<n;i++){
            char ss[maxn];
            scanf("%s",ss);
            for (int s=0;s<m;s++){
                a[i][s]=ss[s]-'0';
            }
        }
        int ans11=0,ans22=0;
        for (int i=0;i<n;i++){
            for (int s=0;s<m;s++){
                if (a[i][s])
                {
                    ans1=1,ans2=0;
                    dfs(i,s);
                    ans11=max(ans11,ans1);
                    ans22=max(ans22,ans2);
                }
            }
        }
        printf("%d %d\n",ans11,ans22);
    }
}

上一题下一题 Hint Code Discuss Stats