/*
#include <stdio.h>
int arr[21][21]={},k=0,p=0,arr1[21][21]={};
int n;
int dir[4][4]={{0,+1,0,-1},{+1,0,-1,0},{+1,+1,-1,-1},{-1,+1,+1,-1}};
void dfs(int i,int j,int m)
{
if(arr[i][j]!=m) return ;
k++;
arr[i][j]=-1;
if(k>5) return ;
dfs(i+dir[n][0],j+dir[n][1],m);
dfs(i+dir[n][2],j+dir[n][3],m);
return ;
}
void f()
{
for(int i=1;i<=19;i++)
for(int j=1;j<=19;j++)
arr[i][j]=arr1[i][j];
}
int main()
{
int m,v,a,b;
for(int i=1;i<=19;i++)
for(int j=1;j<=19;j++)
scanf("%d",&arr[i][j]);
for(int i=1;i<=19;i++)
for(int j=1;j<=19;j++)
arr1[i][j]=arr[i][j];
for(int j=1;j<=19;j++){
for(int i=1;i<=19;i++){
m=arr[i][j];
if(m!=0){
for(n=0;n<4;n++){
f();
k=0;
dfs(i,j,m);
if(k==5){
a=i;
b=j;
break;
}
}
}
if(k==5) break;
}
if(k==5) break;
}
if(k==5) printf("%d\n%d %d",m,a,b);
else printf("0");
return 0;
}
*/
/*
#include <stdio.h>
int k,i,j,n,pi,pj,arr[11][11]={},p[9]={0},q,t,t1;
int d[4][4]={{0,+1},{0,-1},{1,0},{-1,0}},a,b;
void f(int i,int j,int a,int b)
{
if(b<0) return ;
if(i>10||i<1) return ;
if(j>10||j<1) return ;
b--;
if(arr[i][j]==-1) return ;
if(arr[i][j]>0) f(i+d[a][0],j+d[a][1],a,b);
if(arr[i][j]==0||arr[i][j]==-2){
arr[i][j]=-2;
f(i+d[a][0],j+d[a][1],a,b);
}
return ;
}
int main()
{
for(i=1;i<=10;i++)
for(j=1;j<=10;j++)
scanf("%d",&arr[i][j]);
for(i=1;i<=10;i++){
for(j=1;j<=10;j++){
t=arr[i][j];
if(t<=0) continue;
else{
t1=t;
arr[i][j]=-2;
for(a=0;a<4;a++){
f(i,j,a,t1);
}
}
}
}
scanf("%d",&n);
for(k=1;k<=n;k++){
scanf("%d %d",&pi,&pj);
if(arr[pi][pj]==0) {
arr[pi][pj]=k;
p[k]=1;
}
else continue;
}
for(i=1;i<=10;i++){
for(j=1;j<=10;j++)
printf("%d ",arr[i][j]);
printf("\n");
}
printf("Character Information\n");
for(k=1;k<=n;k++){
printf("player %d ",k);
if(p[k]==0) printf("dead");
else printf("survive");
printf("\n");
}
return 0;
}
//
#include <stdio.h>
int arr[11][11]={},r,c,i,j,p=0;
int str[11][11]={},v[11][11]={},vo[11][11]={},voi[11][11]={};
int d[8][2]={{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}};
void dfs(int r,int c)
{
if(v[r][c]==1) return ;
v[r][c]=1;
if(r<1||r>9||c<1||c>9) return ;
if(arr[r][c]==1){
for(int i=0;i<8;i++){
if(arr[r+d[i][0]][c+d[i][1]]==0){
str[r+d[i][0]][c+d[i][1]]++;
}
}
return ;
}
for(int i=0;i<8;i++){
if(v[r+d[i][0]][c+d[i][1]]==0)
dfs(r+d[i][0],c+d[i][1]);
}
if(str[r][c]!=0) return ;
vo[r][c]=1;
return ;
}
int main()
{
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
scanf("%d",&arr[i][j]);
scanf("%d %d",&r,&c);
p=0;
for(int i=0;i<8;i++){
if(arr[r+d[i][0]][c+d[i][1]]==1){
p++;
}
}
if(arr[r][c]==1){
for(i=1;i<=9;i++){
for(j=1;j<=9;j++)
if(i==r&&j==c) printf("-1 ");
else printf("_ ");
printf("\n");
}
}
else if(p!=0){
for(i=1;i<=9;i++){
for(j=1;j<=9;j++)
if(i==r&&j==c) printf("%d ",p);
else printf("_ ");
printf("\n");
}
}
else{
dfs(r,c);
for(i=1;i<=9;i++){
for(j=1;j<=9;j++){
for(int u=0;u<8;u++){
if(vo[i][j]==0&&vo[i+d[u][0]][j+d[u][1]]==1){
voi[i][j]=1;
break;
}
}
if(v[i][j]==0||arr[i][j]==1||voi[i][j]==0&&vo[i][j]==0) printf("_ ");
else printf("%d ",str[i][j]);
}
printf("\n");
}
}
return 0;
}
queue
------------------------
1 2 5 3 6
-------------------------
f,r
2
5
3
6
queue (isempty?) f==r
*/
/*
#include <stdio.h>
int n,arr[102][102]={},v[102]={},f=0,r=0,q[102]={};
//queue
void push(int n)
{
r++;
q[r]=n;
return ;
}
int pop()
{
f++;
return q[f];
}
void bfs(int node)
{
for(int i=1;i<=n;i++){
if(v[i]==0&&arr[i][node]==1){
push(i);
v[i]=1;
}
}
return ;
}
int main()
{
int m,a,b,c=0;
scanf("%d",&n);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d %d",&a,&b);
arr[a][b]=1;
arr[b][a]=1;
}
v[1]=1;
bfs(1);
while(f!=r)
{
int x = pop();
printf("%d ",x);
bfs(x);
}
for(int i=2;i<=n;i++){
if(v[i]==1) c++;
}
printf("%d",c);
}
arr[a][b]
1.
int queue[10000][2]={};
rear++;
queue[rear][0]=a;
queue[rear][1]=b;
2.
int queue[10000000]={};
queue[rear]=a*10000+b;
ex arr[57][31] -> 00570031
3. 구조체 배열로 큐 구현
typedef struct
{
int i, j;
}node;
node queue[10000];
rear++;
queue[rear].i=a;
queue[rear].j=b;
*/
#include <stdio.h>
int arr[1002][1002]={},n,m,i,j,q[10000001]={},f=0,r=0,l=0;
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void push(int n)
{
r++;
q[r]=n;
return ;
}
int pop()
{
f++;
return q[f];
}
void bfs(int x)
{
//printf("%d %d %d\n",x,x/10000,x%10000);
for(int i=0;i<4;i++){
if(x/10000+d[i][0]>0&&x/10000+d[i][0]<=m&&x%10000+d[i][1]>0&&x%10000+d[i][1]<=n){
if(arr[x/10000+d[i][0]][x%10000+d[i][1]]==0){
arr[x/10000+d[i][0]][x%10000+d[i][1]]=1;
push(10000*(x/10000+d[i][0])+x%10000+d[i][1]);
}
}
}
//pri();
return ;
}
void pri()
{
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
printf("%d",arr[i][j]);
printf("\n");
}
printf("\n");
return;
}
int main()
{
scanf("%d %d",&m,&n);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf("%d",&arr[i][j]);
if(arr[i][j]==1) push(10000*i+j);
}
if(f==r) printf("-1");
else{
while(f!=r)
{
int k=pop();
bfs(k);
l++;
}
printf("%d",l);
}
return 0;
}