Cod sursa(job #2339689)

Utilizator CristianSoareSoare Cristian Costantin CristianSoare Data 9 februarie 2019 11:07:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <fstream>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin ("insule.in");
ofstream fout("insule.out");

struct pos{
    int lin, col;
};

pos C[106*106], p, s;

char a[105][105];
int NR, NG, NB, b[105][105], prim, ultim, c[105][105], n, m;
int v[] = {-1, 0, 1,  0};
int o[] = { 0, 1, 0, -1};

void fill(int i, int j, char c){
	int k;
	b[i][j] = 1;
	for(k = 0; k < 4; ++k){
		int _i = i + v[k];
		int _j = j + o[k];
		if (a[_i][_j] == c && b[_i][_j] == 0 && a[_i][_j] != '?')
            fill(_i, _j, c);
	}
}

void Lee(int &Lg){
    int k, i, j;
    while (prim <= ultim){
        i = C[prim].lin;
        j = C[prim].col;
        prim++;
        for (k = 0;k < 4;k++){
            int _i = i + v[k];
            int _j = j + o[k];
            if (a[_i][_j] == '0' && c[_i][_j] == 0 && _i > 0 && _i <= n && _j > 0 && _j <= m && c[i][j]+1 < Lg){
                c[_i][_j] = c[i][j]+1;
                ultim++;
                C[ultim].lin = _i;
                C[ultim].col = _j;
            }
            else if (a[_i][_j] == '2' && c[i][j] != 0 && _i > 0 && _i <= n && _j > 0 && _j <= m)
                if (c[i][j] < Lg)
                    Lg = c[i][j];
        }
    }
}
int main(){
    int i, j, Lg = INF;
    fin >> n >> m;
    for (i = 0;i <= n+1;i++)
        a[0][i] = a[n+1][i] = '?';
    for (i = 0;i <= m+1;i++)
        a[i][0] = a[i][m+1] = '?';
    for (i = 1;i <= n;i++)
        for (j = 1;j <= m;j++){
            fin >> a[i][j];
            if (a[i][j] == '1'){
                C[ultim].lin = i;
                C[ultim].col = j;
                ultim++;
            }
        }
    for (i = 1;i <= n;i++)
        for (j = 1;j <= m;j++){
            if (b[i][j] == 0){
                if (a[i][j] == '1'){
                    fill(i, j, '1');
                    NR++;
                }
                else if (a[i][j] == '2'){
                    fill(i, j, '2');
                    NG++;
                }
                else if (a[i][j] == '3'){
                    fill(i, j, '3');
                    NB++;
                }
            }
        }
    Lee (Lg);
    fout << NR << " " << NG << " " << NB << " " << Lg;
    fin.close();
    fout.close();
    return 0;
}