SDA - hw11 - task2

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>

using namespace std;

bool matrix[1000][1000];

int bigger = INT_MIN;
int counter = 0;
int n, m;

int finalDist[1000][1000];

struct Point {
    int x;
    int y;
    Point(int x, int y) : x(x), y(y){}
    bool operator==(const Point other) const {
        return x == other.x && y == other.y;
    }
    bool operator<(const Point other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

struct comparator {
    bool operator()(pair<int, Point> lhs, pair<int, Point> rhs) const {
        return lhs.first < rhs.first || (lhs.first == rhs.first && lhs < rhs);
    }
};

bool isEnd(Point& point) {
    return point.x == 0 || point.x >= n - 1 || point.y == 0 || point.y >= m - 1;
}

vector<Point> getNeighbours(const Point& point){
    vector<Point> result;
    if (point.x != 0)
        result.push_back(Point(point.x - 1, point.y));
    if (point.x != n - 1)
        result.push_back(Point(point.x + 1, point.y));

    if (point.y != 0)
        result.push_back(Point(point.x, point.y - 1));
    if (point.y != m - 1)
        result.push_back(Point(point.x, point.y + 1));
    return result;
}

int findShortest(const Point& start, vector<vector<int>>& distances) {
    set<pair<int, Point>, comparator> queue; // dist, idx
    queue.insert({ 0, start });
    distances[start.x][start.y] = 0;
    while (!queue.empty())
    {
        auto curr = *queue.begin();
        queue.erase(curr);

        if (isEnd(curr.second))
        {
            return curr.first;
        }

        auto neighbours = getNeighbours(curr.second);
        for (auto& neighbour : neighbours)
        {
            if (finalDist[neighbour.x][neighbour.y] != INT_MAX) {
                queue.insert({ (curr.first + finalDist[neighbour.x][neighbour.y]), Point((neighbour.x + n), (neighbour.y + m))});
                continue;
            }

            int finalTime = curr.first;
            if (!matrix[neighbour.x][neighbour.y]) {
                finalTime++;
            }

            if (finalTime < distances[neighbour.x][neighbour.y])
            {
                auto curr = queue.find({ distances[neighbour.x][neighbour.y], neighbour });
                if (curr != queue.end())
                    queue.erase(curr);
                queue.insert({ finalTime, neighbour });
                distances[neighbour.x][neighbour.y] = finalTime;
            }
        }
    }

    return -1;
}

int main() {
    cin >> n >> m;
    char ch;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> ch;
            matrix[i][j] = (ch == '.');
            finalDist[i][j] = INT_MAX;
        }
    }


    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < m; j++)
        {
            if (matrix[i][j])
            {
                vector<vector<int>> distances(n, vector<int>(m, INT_MAX));
                int dist = findShortest(Point(i, j), distances);
                finalDist[i][j] = dist;
                if (dist > bigger) {
                    bigger = dist;
                    counter = 1;
                }
                else if (dist == bigger) {
                    counter++;
                }
            }
        }
    }

    cout << counter;
    return 0;
}