bjfu1143 小蝌蚪安家 解题报告

搜索没判断重复 导致各种bug 广搜栈空间超了 深搜有调试了半天 真的无语了 记录一下 校内放了链接校外也访问不了 直接放题目

用visit数组记录是否出现在队列里面 数据结构学好 并且做的题目少的可怜

题目出的还不错 经典搜索题目

小蝌蚪安家

时间限制(普通/Java):1000MS/10000MS          运行内存限制:65536KByte 总提交:30            测试通过:10

描述

在一个矩形区域内，有些地方有水，有些地方没水。所有相邻的有水的地方会共同组成一个水洼，小蝌蚪想在这块区域中找到一个最大的水洼来安家。

输入

有多组输入数据，每组第一行包含两个正整数n，m（n，m<=100），接下来n行，每行m个字符，“.”表示有水，“#”表示没水。

输出

对于每组输入数据输出一行，包含一个整数，表示最大的水洼的面积。

样例输入

3 3 ### ### ##. 2 3 #.. ..# 3 3 ##. #.. .##

样例输出

1 4 3

题目来源

jhfjhfjhf1（金海峰出题 比赛的时候居然没看到）

代码

 

/*
  Name:
  Copyright:
  Author:yujiaao
  Date:
  Description:hdu
*/
#include<iostream>
#include<cstdio>
#include <algorithm>
using namespace std;
struct node
{
    int x;
    int y;
};
int n,m;
node queue[200];
char map[200][200];
bool is_visit[200][200]={0};
int f[4][2]={-1,0, 0,1, 1,0, 0,-1};
int bfs(int x0,int y0)
{
    int ans=0;
    int i=0;
    int base=0;
    int top=1;
    int x,y;
    queue[base].x=x0;
    queue[base].y=y0;
    is_visit[queue[base].x][queue[base].y]=1;
    while(base!=top)
    {
        ans++;
        for(i=0;i<4;i++)
        {
            x=queue[base].x+f[i][0];
            y=queue[base].y+f[i][1];
            if(x>=0 && x<n && y>=0 && y<m && map[x][y]=='.' && is_visit[x][y]==0 )
            {
                is_visit[x][y]=1;
                queue[top].x=x;
                queue[top].y=y;
                top++;
            }
        }
        map[queue[base].x][queue[base].y]='#';
        base++;
    }
    return ans;
}
int main()
{
//    freopen("C:\\Users\\yujiaao\\Desktop\\测试专用\\in.txt","r",stdin);
//    freopen("C:\\Users\\yujiaao\\Desktop\\测试专用\\out.txt","w",stdout);
    int max,i,j,temp;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(queue,0,sizeof(queue));
        memset(is_visit,0,sizeof(is_visit));
        getchar();
        max=0;
        for(i=0;i<200;i++)
        {
            for(j=0;j<200;j++)
            {
                map[i][j]=0;
            }
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                scanf("%c",&map[i][j]);
            }
            getchar();
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(map[i][j]=='.')
                {
                    temp=bfs(i,j);
                    if(temp>max)
                    max=temp;
                }
            }
        }
        printf("%d\n",max);
    }
    //system("pause");
    return 0;
}