CSES - Counting Rooms | Đếm phòng

Xem PDF



Thời gian:
Python 3 2.0s
Bộ nhớ:
Python 3 500M

Tác giả:
Dạng bài
Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho trước bản đồ của một tòa nhà, và nhiệm vụ của bạn là đếm số lượng phòng của nó. Kích thước của bản đồ là \(n \times m\) hình vuông, và mỗi hình vuông là sàn hoặc tường. Bạn có thể đi bộ sang trái, phải, lên trên và xuống dưới qua các ô sàn nhà .

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(m\): kích thước của bản đồ.
  • \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự mô tả bản đồ. Mỗi ký tự là . (sàn) hoặc # (tường).

Output

  • In một số nguyên: số lượng phòng.

Constraints

  • \(1 \leq n, m \leq 1000\)

Example

Sample input

5 8
########
#..#...#
####.#.#
#..#...#
########

Sample output

3


Bình luận


  • -3
    penistone 6:50 p.m. 8 Tháng 1, 2024 đã chỉnh sửa

    C++

    #include<bits/stdc++.h>
    #define int long long
    #define endl "\n"
    using namespace std;
    int f[2001][2001]={};
    void fill(int i, int j)
    {
        f[i][j]=2;
        if (f[i+1][j]==1) fill(i+1,j);
        if (f[i-1][j]==1) fill(i-1,j);
        if (f[i][j+1]==1) fill(i,j+1);
        if (f[i][j-1]==1) fill(i,j-1);
    }
    signed main()
    {
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int n,m,i,j,res=0; char a;
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                cin>>a;
                if (a=='#') f[i][j]=2; else f[i][j]=1;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if (f[i][j]==1) { res++; fill(i,j); }
            }
        }
        cout<<res;
        return 0;
    }