Map.cpp

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define vii vector<vi>
#define ii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define stoi stoll
#define popcnt __builtin_popcount
#define getbit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
#define FOR(i,j,k) for(int i=j; i<(int)k; ++i)
#define look(a) cerr <<#a<<": "<<a<<endl;
#define look2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;

struct Node
{
    int x;
    int y;
};

struct queueNode
{
    Node p;
    int count;
};

int n,m;
Node c,d;

bool valid(int x, int y)
{
    return x >= 0 && x < n &&
           y >= 0 && y < m;
}

int BFS(vii a, Node c, Node d)
{
    bool v[n][m];
    memset(v,0,sizeof(v));
    v[c.x][c.y] = true;

    queue<queueNode> q;
    queueNode s = {c,-1};
    q.push(s);
    while(!q.empty())
    {
        queueNode curr = q.front();
        Node pt = curr.p;

        if (pt.x == d.x && pt.y == d.y)
            return curr.count;

        q.pop();

        int i;

        i = pt.x-1;
        while (valid(i,pt.y) && a[i][pt.y] && !v[i][pt.y]) --i;
        for (int j = pt.x-1; j > i; --j){
                v[j][pt.y] = true;
                queueNode next = {{j,pt.y},curr.count+1};
                q.push(next);
            }

        i = pt.x+1;
        while (valid(i,pt.y) && a[i][pt.y] && !v[i][pt.y]) ++i;
        for (int j = pt.x+1; j < i; ++j){
                v[j][pt.y] = true;
                queueNode next = {{j,pt.y},curr.count+1};
                q.push(next);
            }

        i = pt.y-1;
        while (valid(pt.x,i) && a[pt.x][i] && !v[pt.x][i]) --i;
        for (int j = pt.y-1; j > i; --j){
                v[pt.x][j] = true;
                queueNode next = {{pt.x,j},curr.count+1};
                q.push(next);
            }

        i = pt.y+1;
        while (valid(pt.x,i) && a[pt.x][i] && !v[pt.x][i]) ++i;
        for (int j = pt.y+1; j < i; ++j){
                v[pt.x][j] = true;
                queueNode next = {{pt.x,j},curr.count+1};
                q.push(next);
            }
    }
    return -1;
}

void solve()
{
    cin >> n >> m;
    vii a(n,vi(m,0));
    FOR(i,0,n){
        string x;
        cin >> x;
        FOR(j,0,m){
            a[i][j] = (x[j] == '#') ? 0 : 1;
            if(x[j] == 'C'){
                c.x = i;
                c.y = j;
            }
            if(x[j] == 'N'){
                d.x = i;
                d.y = j;
            }
        }
    }
    int ans = BFS(a,c,d);

    FOR(i,0,n)


    cout << ans;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    solve();
}