问题标题: 酷町堂：3545 飞机数量

Question

0

已解决

陈泉宏

高级守护

3545   飞机数量

题目描述 Description
在一个N*M的巨大矩阵状空地中，停放着一些飞机，为了日后移动方便，即使土地资源紧张，也不允许一架飞机碰到另一架飞机，不然是很危险的，我们假设所有的飞机都是由#组成的矩形，现在需要你求出这一大片区域中停放的飞机的数量。

输入描述 Input Description
输入第一行由用空格隔开的两个整数N和M组成，这两个数分别表示矩阵的行数和列数。接下来的N行每行包含M个字符，每个字符可以为“#”，也可为“.”，“#”表示飞机的一部分，“.”表示石堆。

输出描述 Output Description
为每一个段落输出一行解。如果飞机的位置放得正确（即矩阵上只存在相互之间不能接触的方形，如果两个“#”号上下相邻或左右相邻却分属两架不同的飞机，则称这两架飞机相互接触了）。就输出一段话“There are S planes.”,S表示飞机的数量。否则输出“Bad placement.”。

样例输入 Sample Input
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#

样例输出 Sample Output
There are 5 planes.

数据范围及提示 Data Size & Hint
1≤N,M≤1000
#include<iostream>
using namespace std;
char a[101][101];
bool used[101][101];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
void dfs(int x,int y)
{
    used[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!used[nx][ny]&&a[nx][ny]=='#')
        {
            dfs(nx,ny);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            used[i][j]=false;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='#'&&!used[i][j])
            {
                ans++;
                dfs(i,j);
            }
        }
    }
    if(ans>=2)cout<<"There are "<<ans<<" planes.";
    else if(ans==1)cout<<"There is "<<ans<<" plane.";
    else if(ans==0)cout<<"Bad placement.";
    return 0;
}

如何求飞机是否接触？

Answer 1

已采纳

张睿杰

初级天翼

这个你可以把这个矩形的四条边的长度记下来，判断里面是不是全都是‘#’号

主程序关键

if(a[i][j]=='#'&&!f[i][j])
{
    cnt=0;
    minx=100000,miny=100000,maxx=-1,maxy=-1;
    ans++;
    dfs(i,j);
    if((maxx-minx+1)*(maxy-miny+1)!=cnt){
        cout<<"Bad placement."<<endl;
        return 0;
    }
}

搜索关键

cnt++;
minx=min(minx,x);
miny=min(miny,y);
maxx=max(maxx,x);
maxy=max(maxy,y);
f[x][y]=1;
for(int i=1;i<=4;i++){
    int nx=x+dir[i][0],ny=y+dir[i][1];
    if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!f[nx][ny]&&a[nx][ny]=='#')
       dfs(nx,ny);
}

Answer 2

王若鸿

初级守护

if((rx - lx + 1) * (ry - ly + 1) == c1) c++;
else cout<<"Bad placement."<<endl;

void DFS(int x,int y){
   a[x][y] = '.';
   c1++;
   lx = min(x,lx);
   ly = min(y,ly);
   rx = max(x,rx);
   ry = max(y,ry);
   int tx,ty;
   for(int i = 1;i <= 4;i++){
       tx = x + fx[i];
       ty = y + fy[i];
       if(a[tx][ty] == '#'){
           DFS(tx,ty);
       }
   }
}

问题标题: 酷町堂：3545 飞机数量

2 个回答: