Pagini recente » Cod sursa (job #2560924) | Cod sursa (job #1849733) | Cod sursa (job #2121843) | Cod sursa (job #1221547) | Cod sursa (job #1402895)
#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;
}