OIG IV - zaj

// https://szkopul.edu.pl/problemset/problem/wQAk4d4zyJLueWkOPiNq_yD7/site/?key=statement
// OIG IV 2 etap (dzień próbny)

#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

constexpr int sizik2 = 1024;

std::string arr[sizik2];

constexpr int sizik = sizik2 * sizik2;
bool visited[sizik];

std::queue<std::pair<int, int>> kolejka;

std::vector<int> odl(sizik, -1);

bool checker(char c) {
    return c == '.' || c == 'n' || c == 'z';
}

void BFS(int x, int y, int m, int n) {
    int d = 0;

    visited[(y + 1) * m + x + 1] = true;
    odl[(y + 1) * m + x + 1] = d;

    kolejka.push({x, y});

    while (!kolejka.empty()) {
        auto w = kolejka.front();

        d = odl[(w.second + 1) * m + w.first + 1] + 1;

        if (w.first + 1 < m && w.second + 2 < n && !visited[(w.second + 1 + 2) * m + w.first + 1 + 1]) {
            if (checker(arr[w.second + 2][w.first + 1])) {
                odl[(w.second + 1 + 2) * m + w.first + 1 + 1] = d;
                kolejka.push({w.first + 1, w.second + 2});
            }
            visited[(w.second + 1 + 2) * m + w.first + 1 + 1] = true;
        }
        if (w.first + 1 < m && w.second - 2 >= 0 && !visited[(w.second + 1 - 2) * m + w.first + 1 + 1]) {
            if (checker(arr[w.second - 2][w.first + 1])) {
                odl[(w.second + 1 - 2) * m + w.first + 1 + 1] = d;
                kolejka.push({w.first + 1, w.second - 2});
            }
            visited[(w.second + 1 - 2) * m + w.first + 1 + 1] = true;
        }
        if (w.first - 1 >= 0 && w.second + 2 < n && !visited[(w.second + 1 + 2) * m + w.first + 1 - 1]) {
            if (checker(arr[w.second + 2][w.first - 1])) {
                odl[(w.second + 1 + 2) * m + w.first + 1 - 1] = d;
                kolejka.push({w.first - 1, w.second + 2});
            }
            visited[(w.second + 1 + 2) * m + w.first + 1 - 1] = true;
        }
        if (w.first - 1 >= 0 && w.second - 2 >= 0 && !visited[(w.second + 1 - 2) * m + w.first + 1 - 1]) {
            if (checker(arr[w.second - 2][w.first - 1])) {
                odl[(w.second + 1 - 2) * m + w.first + 1 - 1] = d;
                kolejka.push({w.first - 1, w.second - 2});
            }
            visited[(w.second + 1 - 2) * m + w.first + 1 - 1] = true;
        }
        if (w.first + 2 < m && w.second + 1 < n && !visited[(w.second + 1 + 1) * m + w.first + 2 + 1]) {
            if (checker(arr[w.second + 1][w.first + 2])) {
                odl[(w.second + 1 + 1) * m + w.first + 2 + 1] = d;
                kolejka.push({w.first + 2, w.second + 1});
            }
            visited[(w.second + 1 + 1) * m + w.first + 2 + 1] = true;
        }
        if (w.first + 2 < m && w.second - 1 >= 0 && !visited[(w.second + 1 - 1) * m + w.first + 1 + 2]) {
            if (checker(arr[w.second - 1][w.first + 2])) {
                odl[(w.second + 1 - 1) * m + w.first + 1 + 2] = d;
                kolejka.push({w.first + 2, w.second - 1});
            }
            visited[(w.second + 1 - 1) * m + w.first + 1 + 2] = true;
        }
        if (w.first - 2 >= 0 && w.second + 1 < n && !visited[(w.second + 1 + 1) * m + w.first + 1 - 2]) {
            if (checker(arr[w.second + 1][w.first - 2])) {
                odl[(w.second + 1 + 1) * m + w.first + 1 - 2] = d;
                kolejka.push({w.first - 2, w.second + 1});
            }
            visited[(w.second + 1 + 1) * m + w.first + 1 - 2] = true;
        }
        if (w.first - 2 >= 0 && w.second - 1 >= 0 && !visited[(w.second + 1 - 1) * m + w.first + 1 - 2]) {
            if (checker(arr[w.second - 1][w.first - 2])) {
                odl[(w.second + 1 - 1) * m + w.first + 1 - 2] = d;
                kolejka.push({w.first - 2, w.second - 1});
            }
            visited[(w.second + 1 - 1) * m + w.first + 1 - 2] = true;
        }

        kolejka.pop();
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, m;
    std::cin >> n >> m;

    int begin_x = -1, end_x = -1;
    int begin_y = -1, end_y = -1;

    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    bool flag = false;
    for (int i = 0; i < n; i++) {
        const std::string& s = arr[i];
        for (int j = 0; j < s.size(); j++) {
            const char c = s[j];
            if (c == 'n') {
                begin_x = j;
                begin_y = i;
            } else if (c == 'z') {
                end_x = j;
                end_y = i;
            }
        }
    }

    BFS(begin_x, begin_y, m, n);

    if (odl[(end_y + 1) * m + end_x + 1] != -1) {
        std::cout << odl[(end_y + 1) * m + end_x + 1] << '\n';
    } else {
        std::cout << "NIE\n";
    }

    return 0;
}