Cod sursa(job #2682300)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 8 decembrie 2020 13:41:55
Problema Castel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
//
//  main.cpp
//  castel
//
//  Created by Eusebiu Rares on 07.12.2020.
//

#include <iostream>
#include <fstream>
#include <queue>

std::fstream in ("castel.in", std::ios::in | std::ios::binary) ;
std::fstream out ("castel.out", std::ios::out) ;

const int nmax = 150 ;
const int dx[] = {0, 0, 1, 0, -1} ;
const int dy[] = {0, 1, 0, -1, 0} ;
using PII = std::pair<int, int> ;

int mat[1 + nmax][1 + nmax] ;
int m, n ;

PII getCoords(int val) {
	PII ret ;
	ret.first = (val - 1) / n + 1 ;
	ret.second = (val - 1) % n + 1 ;
	return ret ;
}

int getVal(PII coord) {
	return (coord.first - 1) * n + coord.second ;
}

std::queue<PII> Q ;
std::vector<int> waiting[1 + nmax * nmax] ;
bool key[1 + nmax * nmax] ;
bool seen[1 + nmax][1 + nmax] ;
int ans ;

void sparge(int xx, int yy) {
	int val(getVal({xx, yy})) ;
	std::vector<int>::iterator it = std::unique (waiting[val].begin(), waiting[val].end()) ;
	waiting[val].resize(std::distance(waiting[val].begin(), it)) ;
	for (auto it : waiting[val]) {
		Q.push(getCoords(it)) ;
		key[it] = 1 ;
		sparge(getCoords(it).first, getCoords(it).second) ;
		seen[getCoords(it).first][getCoords(it).second] = 1 ;
		ans ++ ;
	}
}

bool inbounds(int a, int b) {
	return 1 <= a && a <= m && 1 <= b && b <= n ;
}

void bfs(PII src) {
	Q.push(src) ;
	seen[src.first][src.second] = 1 ;
	ans ++ ;
	key[getVal(src)] = true ;
	while (!Q.empty()) {
		PII top(Q.front()) ;
		Q.pop() ;
		for (int k = 1 ; k <= 4 ; ++ k) {
			int xx(top.first + dx[k]) ;
			int yy(top.second + dy[k]) ;
			if (inbounds(xx, yy) && !seen[xx][yy] && key[mat[xx][yy]]) {
				seen[xx][yy] = 1 ;
				ans ++ ;
				sparge(xx, yy) ;
				key[getVal(std::make_pair(xx, yy))] = 1 ;
				Q.push({xx, yy}) ;
			} else if (!key[getVal(std::make_pair(xx, yy))]) {
				waiting[mat[xx][yy]].push_back(getVal({xx, yy})) ;
			}
		}
	}
}

int main(int argc, const char * argv[]) {
	int start ;
	in >> m >> n >> start ;
	for (int i = 1 ; i <= m ; ++ i) {
		for (int j = 1 ; j <= n ; ++ j) {
			in >> mat[i][j] ;
		}
	}
	bfs(getCoords(start)) ;
	out << ans ;
}