Cod sursa(job #1402895)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 26 martie 2015 22:02:07
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define inFile "castel.in"
#define outFile "castel.out"
#define MAX_N 151

int n, m, k;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
queue < int > q;
vector < int > canOpen[MAX_N * MAX_N];
int key[MAX_N][MAX_N];
int prevRoom[MAX_N * MAX_N];
bool u[MAX_N * MAX_N];

inline int makePair(int i, int j);
inline int getI(int key);
inline int getJ(int key);

int main() {
    ifstream in(inFile);
    ofstream out(outFile);
    
    int i, j, currRoom, nextRoom, nextI, nextJ, countOpen = 0;
    bool found;
    
    in >> n >> m >> k;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            in >> key[i][j];
            prevRoom[makePair(i,j)] = key[i][j];
        }
    }
    
    u[k] = true;
    q.push(k);
    while(!q.empty()) {
        currRoom = q.front();
        q.pop();
        
        for(i = 0; i < canOpen[currRoom].size(); i++) {
            nextRoom = canOpen[currRoom][i];
            u[nextRoom] = true;
            q.push(nextRoom);
        }
        
        for(i = 0; i < 4; i++) {
            nextI = getI(currRoom) + dx[i];
            nextJ = getJ(currRoom) + dy[i];
            if(nextI == 0 || nextJ == 0 || nextI == n+1 || nextJ == m+1) continue;
            
            nextRoom = makePair(nextI, nextJ);
            
            if(!u[nextRoom]) {
                if(u[prevRoom[nextRoom]]) {
                    u[nextRoom] = true;
                    q.push(nextRoom);
                }
                else {
                    for(j = 0; j < canOpen[prevRoom[nextRoom]].size() && canOpen[prevRoom[nextRoom]][j] != nextRoom; j++);
                    if(j == canOpen[prevRoom[nextRoom]].size())
                        canOpen[prevRoom[nextRoom]].push_back(nextRoom);
                }
            }
        }
    }
    
    for(i = 1; i <= n*m; i++)
        if(u[i])
            countOpen++;
    
    out << countOpen <<'\n';
    
    return 0;        
}

inline int makePair(int i, int j) {
    return (i-1)*m + j;
}

inline int getI(int key) {
    if(key % m == 0)
        return key/m;
    return key/m+1;
}

inline int getJ(int key) {
    if(key % m == 0)
        return m;
    return key%m;
}