Cod sursa(job #2361232)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 2 martie 2019 13:56:10
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("castel.in");
ofstream out("castel.out");

const int NMAX = 152;

short D[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
struct cam {
    short x, y;
};
cam needed[NMAX][NMAX];
queue<cam> Q;
vector<cam> access[NMAX][NMAX];
int N, M, K;
bool visited[NMAX][NMAX];

cam convertFromNumber(short x) {
    int i = (x-1) / N + 1,
        j = x % N;
    return {i, ((j == 0) ? N : j)};
}

int convertToNumber(const cam& a) {
    return ((a.x - 1) * N + a.y);
}

void bord() {
    for(int i = 1; i <= N; i++)
        visited[0][i] = visited[M+1][i] = 1;
    for(int i = 1; i <= M; i++)
        visited[i][0] = visited[i][N+1] = 1;
}

int bfs(const cam& start) {
    visited[start.x][start.y] = 1;
    Q.push(start);
    cam crt, vec, aux;
    int R = 1;
    while(!Q.empty()) {
        crt = Q.front();
        Q.pop();
        while(!access[crt.x][crt.y].empty()) {
            vec = access[crt.x][crt.y].back();
            if(!visited[vec.x][vec.y]) {
                visited[vec.x][vec.y] = 1;
                Q.push(vec);
                R++;
            }
            access[crt.x][crt.y].pop_back();
        }

        for(int k = 0; k < 4; k++) {
            vec.x = crt.x + D[k][0];
            vec.y = crt.y + D[k][1];

            if(!visited[vec.x][vec.y]) {
                aux = needed[vec.x][vec.y];

                if(visited[aux.x][aux.y]) {
                    visited[vec.x][vec.y] = 1;
                    Q.push(vec);
                    R++;
                } else access[aux.x][aux.y].push_back(vec);
            }
        }
    }
    return R;
}

int main() {
    in >> M >> N >> K;
    int x;
    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= N; j++) {
            in >> x;
            needed[i][j] = convertFromNumber(x);
        }
    cam start = convertFromNumber(K);

    out << bfs(start) << '\n';
}