#include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; int M, N, K; int map[101][101]; bool check[101][101]; int ans = 0; vector<int> v; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; void cal(int a, int b, int c, int d) { int x1 = a; int y1 = b; int x2 = c - 1; int y2 = d - 1;
for (int x = x1; x <= x2; x++) { for (int y = y1; y <= y2; y++) { map[x][y] = 1; } }
return; } void dfs(int x, int y, int len) {
ans = max(ans, len);
for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < N && ny < M && check[nx][ny] == false && map[nx][ny] == 0) { check[nx][ny] = true; len += 1;
dfs(nx, ny, len); } }
return; } int main() { freopen("input.txt", "r", stdin); cin >> M >> N >> K;
for (int i = 0; i < 101; i++) { for (int j = 0; j < 101; j++) { map[i][j] = -1; } }
for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { map[i][j] = 0; } }
for (int i = 0; i < K; i++) { int a, b, c, d; cin >> a >> b >> c >> d; cal(a,b,c,d); }
for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (map[i][j] == 0 && check[i][j]==false) { ans = 0;
check[i][j] = true; dfs(i, j, 1);
v.push_back(ans); } } }
sort(v.begin(), v.end()); cout << v.size() << endl; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl;
his130 6년 전
위의 코드는 불합격.
아래의 코드는 합격 코드 입니다.
단지 len이라는 함수를 전역함수로 바꾸기만 했는데..
통과되는 이유를 모르겠어요..
len을 dfs함수 안에 넣어서 돌려도 똑같은거 같은데...ㅠㅠㅠ
제발 알려주세요...ㅠㅠㅠ
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int M, N, K;
int map[101][101];
bool check[101][101];
int ans = 0;
vector<int> v;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
void cal(int a, int b, int c, int d)
{
int x1 = a;
int y1 = b;
int x2 = c - 1;
int y2 = d - 1;
for (int x = x1; x <= x2; x++)
{
for (int y = y1; y <= y2; y++)
{
map[x][y] = 1;
}
}
return;
}
void dfs(int x, int y, int len)
{
ans = max(ans, len);
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < M && check[nx][ny] == false && map[nx][ny] == 0)
{
check[nx][ny] = true;
len += 1;
dfs(nx, ny, len);
}
}
return;
}
int main()
{
freopen("input.txt", "r", stdin);
cin >> M >> N >> K;
for (int i = 0; i < 101; i++)
{
for (int j = 0; j < 101; j++)
{
map[i][j] = -1;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
map[i][j] = 0;
}
}
for (int i = 0; i < K; i++)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
cal(a,b,c,d);
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (map[i][j] == 0 && check[i][j]==false)
{
ans = 0;
check[i][j] = true;
dfs(i, j, 1);
v.push_back(ans);
}
}
}
sort(v.begin(), v.end());
cout << v.size() << endl;
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
return 0;
}