Cod sursa(job #2806509)

Utilizator TghicaGhica Tudor Tghica Data 22 noiembrie 2021 18:40:54
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include<fstream>
#include<algorithm>

using namespace std;

int blocat[754][754];

int h[753][753], dl[] = { 0, 0, 1, -1 }, dc[] = { 1, -1, 0, 0 }, sum, mn;

void ffBloc(int x, int y) {
	int i;
	blocat[x][y] = -1;
	for (i = 0; i < 4; i++) {
		if (h[x][y] <= h[x + dl[i]][y + dc[i]] && blocat[x + dl[i]][y + dc[i]] == 0) {
			ffBloc(x + dl[i], y + dc[i]);
		}
	}
	return;
}

void mnfind(int x, int y) {
	int i;
	blocat[x][y] = 1;
	for (i = 0; i < 4; i++) {
		if (blocat[x + dl[i]][y + dc[i]] == -1) {
			mn = min(mn, h[x + dl[i]][y + dc[i]]);
		} else if (blocat[x + dl[i]][y + dc[i]] == 0) {
			mnfind(x + dl[i], y + dc[i]);
		}
	}
	return;
}

void sumFind(int x, int y) {
	int i;
	blocat[x][y] = -1;
	if (h[x][y] < mn)
		sum += mn - h[x][y];
	for (i = 0; i < 4; i++) {
		if (blocat[x + dl[i]][y + dc[i]] == 1) {
			sumFind(x + dl[i], y + dc[i]);
		}
	}
	return;
}

int main() {
	ifstream cin("volum.in");
	ofstream cout("volum.out");
	int i, j, n, m, x, y, rez;
	cin >> n >> m;
	for (i = 0; i <= n + 1; i++) {
		blocat[i][0] = -1;
		blocat[i][m + 1] = -1;
	}
	for (j = 0; j <= m + 1; j++) {
		blocat[0][j] = -1;
		blocat[m + 1][j] = -1;
	}
	mn = 2100000000;
	for ( i = 1; i <= n; i++ ) {
		for (j = 1; j <= m; j++) {
			cin >> h[i][j];
		}
	}
	for (i = 1; i <= n; i++) {
		if (blocat[i][1] == 0) {
			ffBloc(i, 1);
		}
		if (blocat[i][m] == 0) {
			ffBloc(i, m);
		}
	}
	for (i = 1; i <= m; i++) {
		if (blocat[1][i] == 0) {
			ffBloc(1, i);
		}
		if (blocat[n][i] == 0) {
			ffBloc(n, i);
		}
	}
	rez = 0;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (blocat[i][j] == 0) {
				mn = 2100000000;
				mnfind(i, j);
				sum = 0;
				sumFind(i, j);
				rez += sum;
			}
		}
	}
	cout << rez;
}