felix24mihai
Prava Felix Mihai
• felix24mihai
logout | contul meu
infoarena informatica de performanta
infoarena
blog
forum
calendar
profilul meu
mesaje
Home
Arhiva de probleme
Arhiva educatională
Arhiva monthly
Arhiva ACM
Concursuri
Concursuri virtuale
Clasament
Articole
Downloads
Links
Documentaţie
Despre infoarena
Monitorul de evaluare
Trimite soluţii
Contul meu
! Cautare
 
In curand...
139762 membri inregistrati

08:50:44
Fii un bun infoarenaut! Implică-te!

Pagini recente » Borderou de evaluare (job #2750463) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #2750463)

Cod sursa(job #2750463)
Utilizator	felix24mihaiPrava Felix Mihai felix24mihai	Data	11 mai 2021 13:48:02
Problema	Barbar	Scor	90
Compilator	cpp-64	Status	done
Runda	Arhiva de probleme	Marime	3.12 kb
Raporteaza aceasta sursa
#include <iostream>
#include <queue>
#include <fstream>
#include <bits/stdc++.h>
#define NMAX 1005
using namespace std;
ifstream f("barbar.in");
ofstream g("barbar.out");
int n, line, column, startLine, startColumn, inputMatrix[NMAX][NMAX];
int finishLine, finishColumn, dragonMatrix[NMAX][NMAX];
int dlin[4] = { 0, 1, 0, -1 };
int dcol[4] = { 1, 0, -1, 0 };
queue <pair<int, int>> dragons;
void read(){
	f >> line >> column;
	char c;
	for (int i = 1; i <= line; i++){
		for (int j = 1; j <= column; j++){
			f >> c;
			if (c == '.'){
				inputMatrix[i][j] = 0;
			} else if (c == '*'){
				inputMatrix[i][j] = -8;
			} else if (c == 'D'){
				inputMatrix[i][j] = -7;
				dragons.push(make_pair(i,j));
			} else if (c == 'I'){
				inputMatrix[i][j] = 0;
				startLine = i;
				startColumn = j;
			} else if (c == 'O'){
				inputMatrix[i][j] = 0;
				finishLine = i;
				finishColumn = j;
			}
		}
	}
}
int minPathMatrix[NMAX][NMAX];
void border(){
	for (int j = 0; j <= column + 1; j++){
		inputMatrix[0][j] = -1;
		inputMatrix[line + 1][j] = -1;
	}
	for (int i = 0; i <= line + 1; i++){
		inputMatrix[i][0] = -1;
		inputMatrix[i][column + 1] = -1;
	}
}
void dragonBFS(){
	while(!dragons.empty()){
		int line = dragons.front().first;
		int column = dragons.front().second;
		dragons.pop();
		for (int i = 0; i < 4; i++){
			int newLine = line + dlin[i];
			int newColumn = column + dcol[i];
			if (inputMatrix[newLine][newColumn] == 0){
				int currentPrison = dragonMatrix[line][column];
				int nextPrison = dragonMatrix[newLine][newColumn];
				if (nextPrison == 0){
					dragonMatrix[newLine][newColumn] = dragonMatrix[line][column] + 1;
					dragons.push(make_pair(newLine, newColumn));
				}
			}
		}
	}
}
void manBFS(int lineS, int columnS){
	queue <pair<int, int>> q;
	q.push(make_pair(lineS, columnS));
	minPathMatrix[lineS][columnS] = dragonMatrix[lineS][columnS];
	while(!q.empty()){
		int line = q.front().first;
		int column = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++){
			int newLine = line + dlin[i];
			int newColumn = column + dcol[i];
			if (inputMatrix[newLine][newColumn] == 0){
				if (minPathMatrix[line][column] == 0){
					int currentPathMatrix = minPathMatrix[line][column];
					int nextPrison = dragonMatrix[newLine][newColumn]; 
					minPathMatrix[newLine][newColumn] = min(currentPathMatrix, nextPrison);
					q.push(make_pair(newLine, newColumn));
				} else{
					int currentMinPath = minPathMatrix[line][column];
					int nextPrison = dragonMatrix[newLine][newColumn];
					int nextMinPath = minPathMatrix[newLine][newColumn];
					if (nextMinPath < currentMinPath && nextMinPath < nextPrison){
						minPathMatrix[newLine][newColumn] = min(currentMinPath, nextPrison);
						q.push(make_pair(newLine, newColumn));
					}
				}
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
	read();
	border();
	dragonBFS();
	manBFS(startLine, startColumn);
	if (minPathMatrix[finishLine][finishColumn] == 0)
		g << -1;
	else 
		g << minPathMatrix[finishLine][finishColumn];
	return 0;
}
© 2004-2021 Asociatia infoarenaPrima paginaDespre infoarenaTermeni si conditiiContactSari la inceputul paginii ↑
Creative Commons LicenseCu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
este publicat sub licenta Creative Commons Attribution-NonCommercial 2.5.