include
include
include
include
using namespace std;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main()
{
int T,i,j,N,M;
for(scanf("%d",&T);T>0;T--)
{int p=0,k=0;
scanf("%d%d",&N,&M);
int a[N][M],v[N][M],b[N][M];
for(i=0;i<N;i++)
for(j=0;j<M;j++)
{scanf("%d",&a[i][j]);
v[i][j]=0;b[i][j]=0;
}
for(i=0;i<N;i++)
{for(j=0;j<M;j++)
{k=0;
if(a[i][j]==1)
{
b[i][j]=0;
continue;
}
else//a[i][j]==0 ie black
{
int e,r;
for(e=0;e<N;e++)
for(r=0;r<M;r++)
v[e][r]=0;
//
queue < pair<int,int> >q; k=0;
q.push(make_pair(i,j));
v[i][j]=1;
while(!q.empty())
{
pair<int,int> t=q.front();
q.pop();
int x=t.first;int y=t.second;
for(p=0;p<4;p++)
{
int x1=x+dx[p];int y1=y+dy[p];
if(x1>=0 && x1<N && y1>=0 && y1<M)
{if(v[x1][y1]==0 && a[x1][y1]==1)
{
k=v[x][y];break;
}
else if(v[x1][y1]==0 && a[x1][y1]==0)
{
v[x1][y1]=v[x][y]+1;
q.push(make_pair(x1,y1));
}
}
}
/*
for(e=0;e<N;e++)
{for(r=0;r<M;r++)
printf("%d\t",v[e][r]);
printf("\n");
}
printf("\n");
*/
if(k>0) break;
}
b[i][j]=k;
//
}//else
}
}
for(i=0;i<N;i++)
{for(j=0;j<M;j++)
printf("%d ",b[i][j]);
printf("\n");
}
}
return 0;
}
/**
?? I am not able to find the error for "sigsegv" , don't know where it is giving out of bound;
I know it will give TLE , but there is some runtime error.
Here I have done brute-force method.Just travesed all the nodes
If it is 1 simply get 0 for it.
if it is 0 , then run a bfs on that node staring from assigning it 1 , next wave will be 2,
,then next wave will be 3 ..so on .
whereever you get a[][]==1 in the wave ,stop ,break and assign the value of last wave no.
**/