Cod sursa(job #1923665)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 11 martie 2017 21:02:18
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MaxK 23000
#define MaxN 155
using namespace std;
   
FILE*IN,*OUT;

int N,M,K,Mat[MaxN][MaxN],Out=0;
bool found[MaxK],Vis[MaxN][MaxN];
queue<pair<int,int> >List[MaxK];
queue<pair<int,int> >Q;
void BFS()
{
	int X,Y;
	while(!Q.empty())
	{
		X=Q.front().first;
		Y=Q.front().second;
		Q.pop();
		if(Vis[X][Y])continue;
		Vis[X][Y]=true;
		Out++;
		found[X*M+Y+1]=true;
		while(List[X*M+Y+1].size()>0)
		{
			Q.push(List[X*M+Y+1].front());
			List[X*M+Y+1].pop();
		}
		if(X>0&&!Vis[X-1][Y])
		{
			if(found[Mat[X-1][Y]])
				Q.push(make_pair(X-1,Y));
			else List[Mat[X-1][Y]].push(make_pair(X-1,Y));
		}
		if(X<N-1&&!Vis[X+1][Y])
		{
			if(found[Mat[X+1][Y]])
				Q.push(make_pair(X+1,Y));
			else List[Mat[X+1][Y]].push(make_pair(X+1,Y));
		}
		if(Y>0&&!Vis[X][Y-1])
		{
			if(found[Mat[X][Y-1]])
				Q.push(make_pair(X,Y-1));
			else List[Mat[X][Y-1]].push(make_pair(X,Y-1));
		}
		if(Y<M-1&&!Vis[X][Y+1])
		{
			if(found[Mat[X][Y+1]])
				Q.push(make_pair(X,Y+1));
			else List[Mat[X][Y+1]].push(make_pair(X,Y+1));
		}
	}
}
int main()
{
    IN=fopen("castel.in","r");
    OUT=fopen("castel.out","w");
	
	fscanf(IN,"%d%d%d",&N,&M,&K);
	K--;
	int X=K/M,Y=K%M;
	for(int i=0;i<N;i++)
		for(int j=0;j<M;j++)
			fscanf(IN,"%d",&Mat[i][j]);
	Q.push(make_pair(X,Y));
	BFS();
	fprintf(OUT,"%d",Out);
	return 0;
}