Решение задачи "Грядки" с Меньшиков

Без пояснения   Просмотров: 26


Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Код

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
 
using namespace std;
const char check = '#';
const char uncheck = '.';
vector<string> mas;
int n,m;
void input()
{
    cin>>n>>m;
    mas.resize(n);
    for (int i=0;i<n;i++)
        cin>>mas[i];
}
struct point
{
    int x,y;
    point(){}
    point(int X, int Y)
    {
        x = X; y = Y;
    }
};
int moveX[4] = {-1,0,1,0};
int moveY[4] = {0,-1,0,1};
bool correct(int x, int y)
{
    if (x<0 || y<0)
        return false;
    if (x>=n || y>=m)
        return false;
    return true;
}
void dfs(int fx, int fy)
{
    stack<point> s;
    s.push(point(fx,fy));
    while (!s.empty())
    {
        point cur = s.top();
        s.pop();
        for (int i=0;i<4;i++)
        {
            int x = cur.x + moveX[i];
            int y = cur.y + moveY[i];
            if (correct(x,y) && mas[x][y] == check)
            {
                mas[x][y] = uncheck;
                s.push(point(x,y));
            }
        }
    }
}
void solve()
{
    int amount = 0;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            if (mas[i][j] == check)
            {
                dfs(i,j);
                amount++;
            }
        }
    }
    cout<<amount;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться