Cod sursa(job #507651)
#include <stdio.h>
#include <queue>
#include <string.h>
#define NMAX 205
using namespace std;
int n,D[NMAX][NMAX];
char A[NMAX][NMAX],marc[NMAX][NMAX];
queue <int> Q;
char in[NMAX];
void bf(int x)
{
Q.push(x); in[x]=1;
int i,nod;
while (!Q.empty())
{
nod=Q.front();
Q.pop();
in[nod]=0;
for (i=1; i<=n; i++)
if (nod!=i && A[nod][i]==1)
{
if (D[x][i]>D[x][nod]+1)
{
D[x][i]=D[x][nod]+1;
if (!in[i])
Q.push(i),in[i]=1;
}
}
}
}
void calc_dist()
{
int i,j;
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
D[i][j]=NMAX;
D[i][i]=0;
bf(i);
}
}
inline int verif()
{
int i,j;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (D[i][j]>2)
return 0;
return 1;
}
int main()
{
freopen("oras.in","r",stdin);
freopen("oras.out","w",stdout);
scanf("%d",&n);
int i,j,k,found;
for (i=1; i<=n; i++)
{
for (j=i+1; j<=n; j++)
{
if (!marc[i][j])
{
marc[i][j]=1; marc[j][i]=1;
A[i][j]=1;
found=0;
for (k=1; k<=n; k++)
if (k!=i && k!=j)
{
if (marc[j][k]==1 && A[j][k]==0)
continue ;
if (marc[k][i]==1 && A[k][i]==0)
continue ;
marc[j][k]=1; marc[k][j]=1;
marc[k][i]=1; marc[i][k]=1;
A[j][k]=1; A[k][j]=0; A[k][i]=1; A[i][k]=0;
found=1;
break ;
}
if (!found)
{
for (k=1; k<=n; k++)
if (k!=i && k!=j)
{
if (marc[i][k]==1 && A[i][k]==0)
continue ;
if (marc[k][j]==1 && A[k][j]==0)
continue ;
marc[i][k]=1; marc[k][i]=1;
marc[k][j]=1; marc[j][k]=1;
A[i][k]=1; A[k][i]=0; A[k][j]=1; A[j][k]=0;
break ;
}
}
}
}
}
calc_dist();
if (!verif())
{
printf("-1\n");
return 0;
}
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
printf("%d",A[i][j]);
printf("\n");
}
return 0;
}