Занятие 26.06.2019

#include <iostream> // Для консольного ввода вывода
#include <vector> //Для использования векторов (динамических массивов)
//#include "windows.h"
#include <ctime> //Таймер для генератора случайных чисел
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>

using namespace std; // Пространство имён по умолчанию


struct point
{
    int x;
    int y;
};

vector<vector<bool>> field;
vector<vector<int>> answer;


vector<vector<int>> answer2;

queue < point > _buf[2];

queue< point > _now;
queue< point > _next;

int h, w;

vector<point> cheek(point p0)
{
    vector<point> ret;
    vector<int> x = { -1, 0, 1, 0 };
    vector<int> y = { 0, -1, 0, 1 };
    int i; point p;
    for (i = 0; i < x.size(); ++i)
    {
        p.x = p0.x + x[i];
        p.y = p0.y + y[i];

        if ((p.x < 0) || (p.x >= w)) continue;
        if ((p.y < 0) || (p.y >= h)) continue;

        if ((field[p.y][p.x]) && (answer[p.y][p.x] == -1))
        {
            answer[p.y][p.x] = answer[p0.y][p0.x] + 1;
            ret.push_back(p);
        }

    }

    return (ret);
}

void requ(point p0, int step)
{
    answer2[p0.y][p0.x] = step;

    vector<int> x = { -1, 0, 1, 0 };
    vector<int> y = { 0, -1, 0, 1 };
    int i; point p;
    for (i = 0; i < x.size(); ++i)
    {
        p.x = p0.x + x[i];
        p.y = p0.y + y[i];

        if ((p.x < 0) || (p.x >= w)) continue;
        if ((p.y < 0) || (p.y >= h)) continue;

        if ((field[p.y][p.x]) && (answer2[p.y][p.x] == -1))
        {
            requ(p, step + 1);
        }

    }


}




int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    point p, p0;
    char ch;
    int i ;

    //Высота ширина и начальная точка обхода
    cin >> h >> w >> p0.x >> p0.y;

    field.resize(h); answer.resize(h); answer2.resize(h);
    for (p.y = 0; p.y < h; ++p.y)
    {
        field[p.y].resize(w); answer[p.y].resize(w); answer2[p.y].resize(w);
        for (p.x = 0; p.x < w; ++p.x)
        {
            answer[p.y][p.x] = -1;
            answer2[p.y][p.x] = -1;
            cin >> ch;
            field[p.y][p.x] = (ch == '*');
        }
    }

    answer[p0.y][p0.x] = 0;

    /*
    //Поиск в ширину (хуже)

    _now.push(p0);

    while (_now.size()>0 || _next.size()>0)
    {
        if (i % 2 == 0)
        {
            while (_now.size() > 0)
            {
                for (const auto& it: cheek(_now.front()) )
                {
                    _next.push(it);
                }
                _now.pop();
            }
            ++i;
        }
        else
        {
            while (_next.size() > 0)
            {
                for (const auto& it : cheek(_next.front()))
                {
                    _now.push(it);
                }
                _next.pop();
            }
            ++i;
        }

    }*/

    //Поиск в ширину
    i = 0;
    _buf[0].push(p0);

    while (_buf[0].size()+_buf[1].size()>0)
    {

        while (_buf[i % 2].size() > 0)
        {
            for (const auto& it : cheek(_buf[i % 2].front()))
            {
                _buf[(i+1) % 2].push(it);
            }
            _buf[i % 2].pop();
        }
        ++i;

    }

    cout << "Вывод результата поиска в ширину" << endl;
    for (p.y = 0; p.y < h; ++p.y)
    {
        for (p.x = 0; p.x < w; ++p.x)
        {
            cout<<answer[p.y][p.x]<<"\t";
        }
        cout << endl;
    }

    cout << endl;

    //Поиск в глубину
    requ(p0, 0);


    cout << "Вывод результата поиска в глубину" << endl;
    for (p.y = 0; p.y < h; ++p.y)
    {
        for (p.x = 0; p.x < w; ++p.x)
        {
            cout << answer2[p.y][p.x] << "\t";
        }
        cout << endl;
    }

}