/*
4421- dfs, cnt, 배열값 -1인 것 다 저장해서 더하고 정렬.
#include <stdio.h>
int a[26][26],n, cnt=0;
int co[501]={};
void dfs(int x, int y)
{
if(a[x][y]!=1||x<1||x>n||y<1||y>n) return;
a[x][y]=-1; //이미 방문한 경우 제외.
co[cnt]++; // dfs 할때마다 +1씩.
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main() {
int i, j, temp;
scanf("%d\n", &n);
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
scanf("%1d", &a[i][j]);
}
}
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
if(a[i][j]==1)
{
cnt++;//
dfs(i,j); //ca[]배열이 1, 2, 3이 됨.그래야 정렬(1부터 시작)할 때 안 헷갈림.
}
}
}
printf("%d\n", cnt);
for(i=1; i<cnt; i++) {
for(j=1; j<=cnt-i; j++) {
if(co[j]>co[j+1]) {
temp=co[j];
co[j]=co[j+1];
co[j+1]=temp;
}
}
}
for(i=1; i<=cnt; i++) {
printf("%d\n", co[i]);
}
}
*/
/*
//4060: 검은 색 0의 개수를 상하좌우 탐색, on= 최소 횟수이다. // 모두 끄는 것은 켜져 있는 1의 구역을 상하좌우 탐색, 그때의 off이다.
#include <stdio.h>
int a[101][101], m, n;
void dfs(int x, int y) {
if(a[x][y]!=0||x<1||x>m||y<1||y>n) return;
a[x][y]=-1;
dfs(x-1, y);
dfs(x+1, y);
dfs(x, y-1);
dfs(x, y+1);
}
void last(int x, int y) {
if(a[x][y]!=1||x<1||x>m||y<1||y>n) return;
a[x][y]=-2;
last(x-1, y);
last(x+1, y);
last(x, y-1);
last(x, y+1);
}
int main(){
int i, j, on=0, off=0;
scanf("%d %d", &m, &n);
for(i=1; i<=m; i++) {
for(j=1; j<=n; j++) {
scanf("%d", &a[i][j]);
}
}
for(i=1; i<=m; i++) {
for(j=1; j<=n; j++) {
if(a[i][j]==0) {
dfs(i, j);
on++; }
}
}
for(i=1; i<=m; i++) {
for(j=1; j<=n; j++) {
if(a[i][j]==1) {
last(i, j);
off++; }
}
}
printf("%d %d", on, off);
}
*/
/*
4697 안전영역- 최대값 그냥 main에서 반복문으로 찾기.
#include <stdio.h>
int arr[101][101], n, cnt=0;
int ar[101][101]; // 재귀함수로 다시 배열 초기화 필요.
int i, j;
void copymap() // 한번 탐색 끝나면 배열 초기화
{
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
arr[i][j]=ar[i][j];
}
}
}
void dfs(int x, int y, int h) {
if(arr[x][y]<=h||x<1||x>n||y<1||y>n) return;
arr[x][y]=-1; // 중복 탐색 방지
dfs(x-1, y, h);
dfs(x+1, y, h);
dfs(x, y-1, h);
dfs(x, y+1, h);
}
int main() {
int max=1; // 초기값.
scanf("%d", &n);
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
scanf("%d", &arr[i][j]);
ar[i][j]=arr[i][j];// 또다른 배열 만들어두기.
}
}
for(int k=1;k<=100;k++) // 각 높이별 계산 반복.
{
cnt=0;// cnt 초기화해야 각 높이에 대한 cnt 가능.
copymap(); // 배열 초기화하는 법.
for(i=1; i<=n; i++) {
for(j=1; j<=n; j++) {
if(arr[i][j]>k) {
dfs(i, j, k);
cnt++;
}
}
}
if(max<cnt) {max=cnt;}// 최대값 찾기.
}
printf("%d", max);
}
*/
/*
2610- dfs 한 번 호출하고 끝, 문자를 *로 바꿔서 출력하면 됨.
#include <stdio.h>
char arr[20][20];
void dfs(int a, int b) {
if(arr[a][b]!='_'||a<0||a>=10||b<0||b>=10) return;
arr[a][b]='*';
dfs(a-1, b);
dfs(a+1, b);
dfs(a, b-1);
dfs(a, b+1);
}
int main() {
int a, b; // dfs에서 쓰는 거랑 다름.
int i, j;
for(i=0; i<10; i++) {
for(j=0; j<10; j++){
scanf("%c ", &arr[i][j]); // c하고 스페이스바
}
}
scanf("%d %d", &a, &b);
dfs(b,a); // b, a 바꿔줘야 i, j로 인식 가능.
for(i=0; i<10; i++) {
for(j=0; j<10; j++) {
printf("%c", arr[i][j]);
}
printf("\n");
}
}
*/