poj1856Sea Battle（DFS）

思路：

Description

Input

Output

Sample Input

6 6
.....#
##...#
##...#
..#..#
.....#
######
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#
0 0

Sample Output

Bad placement.
There are 5 ships.

Source

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

const int maxn=1000+10;
char map[maxn][maxn];
int min_x,min_y,max_x,max_y;
int n,m,cal;
int dx[]={-1,1,0,0,-1,-1,1,1};
int dy[]={0,0,-1,1,-1,1,-1,1};

void read_Graph()
{
    char str[maxn];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=m;j++)
           map[i][j]=str[j];
    }
}


bool check(int x,int y)
{
   if(x>=1&&x<=n&&y>=1&&y<=m)
        return true;
   return false;
}

int dfs(int x,int y)
{
    min_x=min(min_x,x);
    max_x=max(max_x,x);
    min_y=min(min_y,y);
    max_y=max(max_y,y);
    map[x][y]='.';
    for(int i=0;i<8;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(map[tx][ty]=='#'&&check(tx,ty))
        {
            cal++;
            dfs(tx,ty);
        }
    }
    return cal;
}

void solve()
{
    int ans=0,area,i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(map[i][j]=='#')
            {
                min_x=max_x=i;
                min_y=max_y=j;
                cal=1;
                area=dfs(i,j);
                if(area==(max_x-min_x+1)*(max_y-min_y+1))
                    ans++;
                else
                {
                    ans=-1;
                    break;
                }
            }
           if(ans==-1)
            break;
        }
    }
    if(ans==-1)
        printf("Bad placement.\n");
    else
        printf("There are %d ships.\n",ans);
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) return 0;
        read_Graph();
        solve();
    }
    return 0;
}