#include <iostream>
/*
입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.
세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.
치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
*/
//int M, N;
//int map[100][100];
//
//int time;
//int cnt_lastcheese;
//int cnt[100];
//void fill(int x, int y)
//{
// // 공기와 접촉된 칸만 녹임
// // c를 찾기
// if (x - 1 > 0) fill(x - 1, y);
// if (x + 1 < N) fill(x + 1, y);
// if (y - 1 > 0) fill(x, y - 1);
// if (y + 1 < N) fill(x, y + 1);
//}
//
//void main()
//{
// freopen("input.txt", "r", stdin);
// setbuf(stdout, NULL);
// scanf("%d %d", &M, &N);
// for (int i = 0; i < M; i++)
// {
// for (int j = 0; j < N; j++)
// {
// scanf("%d", &map[i][j]);
// if (map[i][j] == 1)
// {
// cnt[0]++;
// }
// }
// }
//
// //밖을 채우기
// fill();
// printf("%d", time);
// printf("%d", cnt_lastcheese);
//}
/*
1840 치즈 BFS로 풀기 정올 / 알고리즘
2012.08.05. 23:16
복사http ://blog.naver.com/hero1014/20163651496
번역하기
전용뷰어 보기
치즈
Time Limit : 1000MS
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다.판의 가장자리(<그림 1>에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.치 즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 <그림 2>와 같이 된다.
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모 두 녹아 없어진다.그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모 두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 를 구하는 프로그램을 작성하시오.
입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.세로와 가로의 길이는 최대 100이다.판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
13 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0
0 1 1 1 0 0 0 1 1 0 0 0
0 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
3
5
*/
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
int min = 999;
int map[101][101] = { 0, };//치즈의 위치 입력 받기 위한 2차원 배열
int tx[4000], ty[4000];//큐 3000은 작음
int x[4] = { 0,0,1,-1 };
int y[4] = { 1,-1,0,0 };
int i, j;
int se, ga;//세로 가로의 길이
in >> se >> ga;// input 첫째줄의 세로 가로길이
for (i = 1; i <= se; i++)//세로 읽기
for (j = 1; j <= ga; j++)//가로 읽기
in >> map[i][j];//
int f = 1, s = 1;
tx[f] = 1;//큐 초기값
ty[f] = 1;
int tempx, tempy;
int k;
int cnt;
for (cnt = 0;; cnt++)//치즈가 모두 녹아서 없어지는 데 걸리는 시간
{
f = 1; s = 1;
while (f <= s)// f,s 좌표를 중심으로 하상우좌 순서로 스캔 >> 스캔값 0이면 -1 그리고 >>s는 0의 갯수
{
printf("처음 while 시작 : f = %d , s = %d\n", f, s);
for (i = 0; i<4; i++)
{
tempx = tx[f] + x[i];// tx[1] + {0 0 1 -1}
tempy = ty[f] + y[i];// tx[1] + {1 -1 0 0}
printf("\tif문 : i = %d// tempx= %d , tempy =%d \n", i, tempx, tempy);
if (tempx > 0 && tempx <= se && tempy <= ga && tempy>0 && map[tempx][tempy] == 0)
{
s++;
tx[s] = tempx;
ty[s] = tempy;
map[tempx][tempy] = -1;//이미 읽은 큐는 -1로 바꿔줌
printf("\t****s증가 : %d //map[%d][%d]=0 ////%d\n", s, tempx, tempy, map[tempx][tempy]);
}
}
f++;
printf("f 증가 : %d ", f);
}
int q, l;
k = 0;
for (q = 1; q <= se; q++)//세로 서치
for (l = 1; l <= ga; l++)//가로 서치
{
if (map[q][l] == 1)//치즈 1인 값 찾음
{
f = 1, s = 1;
while (f <= s)
{
for (i = 0; i<4; i++)
{
tempx = q + x[i];
tempy = l + y[i];
if (tempx > 0 && tempx <= se && tempy <= ga && tempy > 0 && map[tempx][tempy] == -1)
{
map[q][l] = 0;
k++;
break;
}
}
f++;
}
}
}
if (k>0 && k<min)
min = k;
int m = 0;
int n = 0;
for (q = 1; q <= se; q++)
{
for (l = 1; l <= ga; l++)
{
if (map[q][l] == -1)
{
m++;
map[q][l] = 0;
}
}
if (m == (se*ga))
n = 1;
}
if (n == 1)
break;
}
out << cnt;//치즈가 모두 녹아서 없어지는 데 걸리는 시간
out << endl;//다음줄
out << min;//모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수
printf("%d , %d", cnt, min);
return 0;
}