Pagini recente » Cod sursa (job #1021452) | Cod sursa (job #19294) | Cod sursa (job #401643) | Cod sursa (job #498630) | Cod sursa (job #2339684)
#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;
}