20250726
//숫자 등고선_BFS (완료)
/*
#include <stdio.h>
#include <string.h>
int s, r=0;
int a[101][101]={};
int queue[10001][2]={};
int front=-1, back=-1;
int px, py;
int c=1;
void push(int h, int r)
{
if(h<1 || h>s || r<1 || r>s || a[h][r]!=0)
return;
back++;
queue[back][0]=h;
queue[back][1]=r;
a[h][r] = c;
}
void pop()
{
if(back==front){
return ;
}
front++;
px = queue[front][0];
py = queue[front][1];
}
void bfs(int x, int y)
{
int index;
push(x, y); //x, y push (front 증가)
while(front!=back){ //queue가 비어있지 않으면 계속 실행
index = back; //back 값을 저장
c++;
for(int i=front; i<index; i++){
pop(); //x, y pop (front 증가)
push(px-1, py); //px-1, py push
push(px, py-1); //px, py-1 push (전부 back 값 증가 및
push(px+1, py); //px+1, py push 등고선 값 들어감)
push(px, py+1); //px, py+1 push
}
}
}
int main()
{
int x, y, i, j;
scanf("%d", &s);
scanf("%d %d", &x, &y);
bfs(x, y);
for(i=1; i<=s; i++){
for(j=1; j<=s; j++){
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
*/
//체스 말 이동
/*
#include <stdio.h>
int main()
{
return 0;
}
*/
//토마토_BFS (진행중)
#include <stdio.h>
#include <string.h>
int s=0, r=0;
int m, n;
int a[1001][1001]={};
int vt[1001][1001]={};
int queue[1000001][2]={0};
int front=-1, back=-1;
int px, py;
int d=0;
void push(int h, int k)
{
if(h<1 || h>n || k<1 || k>m || a[h][k]!=-1 || vt[h][k]==1){
return;
}
back++;
vt[h][k]=1;
queue[back][0]=h;
queue[back][1]=k;
s++;
a[h][k] = 1;
}
void pop()
{
if(back==front){
return ;
}
front++;
px = queue[front][0];
py = queue[front][1];
}
void bfs(int x, int y)
{
push(x, y);
while(1){
pop();
push(px-1, py);
push(px, py-1);
push(px+1, py);
push(px, py+1);
r++;
}
}
int main()
{
int i, j;
scanf("%d %d", &m, &n);
for(i=1; i<=n; i++){
for(j=1; j<=m; j++){
scanf("%d", &a[i][j]);
}
}
for(i=1; i<=n; i++){
for(j=1; j<=m; j++){
if(a[i][j]==1){
d++;
bfs(i, j);
}
}
}
if(d==0){
printf("-1");
}
else if(d==n*m){
printf("1");
}
else{
printf("%d", r);
}
return 0;
}