Pagini recente » Cod sursa (job #3339966) | Cod sursa (job #3312874) | Cod sursa (job #101654) | Cod sursa (job #3338547) | Cod sursa (job #1845288)
#include <fstream>
#include <deque>
#include <vector>
#define NMAX 105
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
using namespace std;
struct point {
int x,y;
};
ifstream fin("vila.in");
ofstream fout("vila.out");
int M[NMAX][NMAX],V[NMAX];
deque < point > Q;
vector < int > A;
inline void Fill(int camera,int x,int y){
int nx,ny;
Q.push_back({x,y});
M[x][y] = camera; V[camera] ++;
while(!Q.empty()){
x = Q.front().x;
y = Q.front().y;
Q.pop_front();
for(int i = 0; i < 4; i++){
nx = x + dx[i];
ny = y + dy[i];
if(M[nx][ny] == 0){
M[nx][ny] = camera;
V[camera] ++;
Q.push_back({nx,ny});
}
}
}
}
inline void cauta(int x, int y){
int j,nx,ny;
for(int i = 0; i < 4; i ++){
nx = x + dx[i];
ny = y + dy[i];
if(M[nx][ny] != -1){
for(j = 0; j < A.size(); j++){
if(A[j] == M[nx][ny])
j = A.size() + 2;
}
if(j != A.size() + 2)
A.push_back(M[nx][ny]);
}
}
}
int main()
{
ios :: sync_with_stdio(false);
fin.tie(NULL);
int n,m;
char x;
fin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
fin >> x;
if(x == '1')
M[i][j] = -1;
}
for(int i = 0; i <= n + 1; i++)
M[i][0] = M[i][m + 1] = -1;
for(int j = 0; j <= m + 1; j++)
M[0][j] = M[n + 1][j] = -1;
int camere = 0,ariemax = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(M[i][j] == 0)
Fill(++camere,i,j);
if(V[camere] > ariemax)
ariemax = V[camere];
}
}
int S = 0,s,xx,yy;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
if(M[i][j] == -1){
s = 0;
cauta(i,j);
for(int k = 0; k < A.size(); k++)
s += V[A[k]];
if(s > S){
S = s;
xx = i; yy = j;
}
A.clear();
}
}
fout << camere << "\n" << ariemax << "\n" << xx << " " << yy <<" "<< S;
return 0;
}