作者在 2011-08-16 15:50:11 发布以下内容
#include <stdio.h>
#include <stdlib.h>
#define MAXQSIZE 64
#define INCREMENT 16
typedef struct node1
{
int x;
int y;
} seat;
typedef struct node2
{
int pre;
seat pos;
} quequetype;
typedef struct node3
{
quequetype *base;
int front;
int rear;
int size;
} Queueptr;
char maze[1000][1000];//全局变量
int m,n;
seat start,end;
void initque(Queueptr &p)
{
p.base=(quequetype *)malloc(MAXQSIZE*sizeof(quequetype));
if(!p.base) exit(0);
p.front= 0;
p.rear=-1;
p.size = MAXQSIZE;
}
int EnQueue(Queueptr &p,quequetype e)
{
if(p.rear == (p.size-1))
{
quequetype *newp;
newp = (quequetype *)realloc(p.base,sizeof(quequetype)*(p.size+INCREMENT));
if(!newp) return 0;
p.base = newp;
p.size += INCREMENT;
}
p.rear++;
p.base[p.rear] = e;
return 1;
}
int QueueEmpty(Queueptr &p)
{
return (p.front==(p.rear+1));
}
int DeQueue(Queueptr &p,quequetype &e)
{
if(QueueEmpty(p)) return 0;
e = p.base[p.front];
p.front++;
return 1;
}
//void GetFront(Queueptr p,quequetype &e)
//{
//e = p.base[p.front];
//}
int GetElem(Queueptr p, int i, quequetype &e)//
{
if (i<0 || i>=p.size) return 0;//控制
e=*(p.base+i);//e取base[i]的值；（包括pos和pre）
return 1;
}
void creatmaze(char maze[][1000],seat &start, seat &end)
{
int i,j;
printf("请输入长和宽：");
scanf("%d%d",&m,&n);
getchar();
printf("请输入迷宫信息：\n");
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
scanf("%c",&maze[i][j]);
getchar();
if (maze[i][j]=='3')
start.x=j,start.y=i;
if (maze[i][j]=='4')
end.x=j,end.y=i;
}
}
}
seat NextPos(seat CurPos, int Di)
{
seat nextPos;
nextPos.y=CurPos.y;
nextPos.x=CurPos.x;
switch (Di)
{
case 1://南
nextPos.y++;
break;
case 2://西
nextPos.x--;
break;
case 3://北
nextPos.y--;
break;
case 4://东
nextPos.x++;
break;
}
return nextPos;
}
int ShortestPath(Queueptr &p, char maze[][1000], seat start, seat end)
{
quequetype e;
seat prePos, curPos;
int i, pre;
initque(p);
curPos = start;
e.pos = curPos;
e.pre = -1;
EnQueue(p, e);
maze[curPos.y][curPos.x]='!';
while (!QueueEmpty(p))
{
pre = p.front;
DeQueue(p, e);
prePos = e.pos;
for (i=1; i<=4; i++)
{
curPos = NextPos(prePos, i);
if (maze[curPos.y][curPos.x]=='0')
{
e.pos = curPos;
e.pre = pre;
EnQueue(p, e);
maze[curPos.y][curPos.x]='!';
}
if (curPos.x == end.x && curPos.y == end.y)
{
e.pos = curPos;
e.pre = pre;
EnQueue(p, e);
maze[curPos.y][curPos.x]='!';
return 1;
}
}
}
return 0;
}
void PrintPath(char maze[][1000], Queueptr &p)
{
int i;
quequetype e;
i=p.rear;//i指队尾；
printf("坐标路径如下：\n");
do
{
if(!GetElem(p,i,e)) exit(0);
printf("(%d,%d)→",e.pos.x,e.pos.y);
maze[e.pos.y][e.pos.x]='&';
i = e.pre;//i指前一个；
}
while (i!=-1); //直到base[0];
printf("\n");
}
void pictype(char ,int i,int j)
{
if((i==start.y&&j==start.x)||(i==end.y&&j==end.x))
{
if(i==start.y&&j==start.x) printf("☆");
if(i==end.y&&j==end.x) printf("★");
}
else
{
if(maze[i][j]=='1') printf("■");
if(maze[i][j]=='0') printf("□");
if(maze[i][j]=='&') printf("⊙");
if(maze[i][j]=='!') printf("▽");
}
}
void print_maze(char maze[][1000])
{
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
{
if(j==n-1)
{
pictype(maze[i][j],i,j);
printf("\n");
}
else
{
pictype(maze[i][j],i,j);
//printf(" ");
}
}
}
void destroyqueue(Queueptr p)
{
free(p.base);
}
int main()
{
int k;
system("color f9");
Queueptr p;
creatmaze(maze,start,end);
printf("你输入的迷宫如下：\n");
print_maze(maze);
k=ShortestPath(p,maze,start,end);
//printf("%d\n",k);
if(k)
PrintPath(maze,p);
printf("路径图如下：\n");
print_maze(maze);
if(!k)
printf("无通路");
destroyqueue(p);
}
/*
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 3 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 1 1 0 1
1 1 1 1 0 0 0 0 1 1
1 1 1 1 1 0 0 0 1 1
1 0 1 0 4 1 0 0 0 1
1 1 0 0 1 0 0 1 1 1
1 0 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
29 29
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1
1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1
1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1
1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1
1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1
1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1
1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1
1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1
1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1
1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1
1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1
1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1
1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1
1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 1
1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1
1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1
1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1
1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1
1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 1 1
1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1
1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 4 0 0 1 1 0 0 0 1 0 1
1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
36 36
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 0 0 0 3 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1
1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1
1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1
1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1
1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1
1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1
1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1
1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1
1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 1
1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1
1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1
1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 1
1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1
1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1
1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1
1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1
1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1
1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1
1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1
1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 1
1 1 0 0 1 0 0 4 0 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1
1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1
1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1
1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1
1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1
1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1
1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1
1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1
1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/
#include <stdlib.h>
#define MAXQSIZE 64
#define INCREMENT 16
typedef struct node1
{
int x;
int y;
} seat;
typedef struct node2
{
int pre;
seat pos;
} quequetype;
typedef struct node3
{
quequetype *base;
int front;
int rear;
int size;
} Queueptr;
char maze[1000][1000];//全局变量
int m,n;
seat start,end;
void initque(Queueptr &p)
{
p.base=(quequetype *)malloc(MAXQSIZE*sizeof(quequetype));
if(!p.base) exit(0);
p.front= 0;
p.rear=-1;
p.size = MAXQSIZE;
}
int EnQueue(Queueptr &p,quequetype e)
{
if(p.rear == (p.size-1))
{
quequetype *newp;
newp = (quequetype *)realloc(p.base,sizeof(quequetype)*(p.size+INCREMENT));
if(!newp) return 0;
p.base = newp;
p.size += INCREMENT;
}
p.rear++;
p.base[p.rear] = e;
return 1;
}
int QueueEmpty(Queueptr &p)
{
return (p.front==(p.rear+1));
}
int DeQueue(Queueptr &p,quequetype &e)
{
if(QueueEmpty(p)) return 0;
e = p.base[p.front];
p.front++;
return 1;
}
//void GetFront(Queueptr p,quequetype &e)
//{
//e = p.base[p.front];
//}
int GetElem(Queueptr p, int i, quequetype &e)//
{
if (i<0 || i>=p.size) return 0;//控制
e=*(p.base+i);//e取base[i]的值；（包括pos和pre）
return 1;
}
void creatmaze(char maze[][1000],seat &start, seat &end)
{
int i,j;
printf("请输入长和宽：");
scanf("%d%d",&m,&n);
getchar();
printf("请输入迷宫信息：\n");
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
scanf("%c",&maze[i][j]);
getchar();
if (maze[i][j]=='3')
start.x=j,start.y=i;
if (maze[i][j]=='4')
end.x=j,end.y=i;
}
}
}
seat NextPos(seat CurPos, int Di)
{
seat nextPos;
nextPos.y=CurPos.y;
nextPos.x=CurPos.x;
switch (Di)
{
case 1://南
nextPos.y++;
break;
case 2://西
nextPos.x--;
break;
case 3://北
nextPos.y--;
break;
case 4://东
nextPos.x++;
break;
}
return nextPos;
}
int ShortestPath(Queueptr &p, char maze[][1000], seat start, seat end)
{
quequetype e;
seat prePos, curPos;
int i, pre;
initque(p);
curPos = start;
e.pos = curPos;
e.pre = -1;
EnQueue(p, e);
maze[curPos.y][curPos.x]='!';
while (!QueueEmpty(p))
{
pre = p.front;
DeQueue(p, e);
prePos = e.pos;
for (i=1; i<=4; i++)
{
curPos = NextPos(prePos, i);
if (maze[curPos.y][curPos.x]=='0')
{
e.pos = curPos;
e.pre = pre;
EnQueue(p, e);
maze[curPos.y][curPos.x]='!';
}
if (curPos.x == end.x && curPos.y == end.y)
{
e.pos = curPos;
e.pre = pre;
EnQueue(p, e);
maze[curPos.y][curPos.x]='!';
return 1;
}
}
}
return 0;
}
void PrintPath(char maze[][1000], Queueptr &p)
{
int i;
quequetype e;
i=p.rear;//i指队尾；
printf("坐标路径如下：\n");
do
{
if(!GetElem(p,i,e)) exit(0);
printf("(%d,%d)→",e.pos.x,e.pos.y);
maze[e.pos.y][e.pos.x]='&';
i = e.pre;//i指前一个；
}
while (i!=-1); //直到base[0];
printf("\n");
}
void pictype(char ,int i,int j)
{
if((i==start.y&&j==start.x)||(i==end.y&&j==end.x))
{
if(i==start.y&&j==start.x) printf("☆");
if(i==end.y&&j==end.x) printf("★");
}
else
{
if(maze[i][j]=='1') printf("■");
if(maze[i][j]=='0') printf("□");
if(maze[i][j]=='&') printf("⊙");
if(maze[i][j]=='!') printf("▽");
}
}
void print_maze(char maze[][1000])
{
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
{
if(j==n-1)
{
pictype(maze[i][j],i,j);
printf("\n");
}
else
{
pictype(maze[i][j],i,j);
//printf(" ");
}
}
}
void destroyqueue(Queueptr p)
{
free(p.base);
}
int main()
{
int k;
system("color f9");
Queueptr p;
creatmaze(maze,start,end);
printf("你输入的迷宫如下：\n");
print_maze(maze);
k=ShortestPath(p,maze,start,end);
//printf("%d\n",k);
if(k)
PrintPath(maze,p);
printf("路径图如下：\n");
print_maze(maze);
if(!k)
printf("无通路");
destroyqueue(p);
}
/*
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 3 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 0 0 0 0 1 1 0 1
1 1 1 1 0 0 0 0 1 1
1 1 1 1 1 0 0 0 1 1
1 0 1 0 4 1 0 0 0 1
1 1 0 0 1 0 0 1 1 1
1 0 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
29 29
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1
1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1
1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1
1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1
1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1
1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1
1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1
1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1
1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1
1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1
1 1 1 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1
1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1
1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1
1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1
1 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 1
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 1
1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1
1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1
1 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1
1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1
1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 1 1
1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1
1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 4 0 0 1 1 0 0 0 1 0 1
1 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
36 36
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 1 1 0 0 0 3 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1
1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1
1 1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1
1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1
1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1
1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1
1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1
1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 1
1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 1
1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1
1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1
1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 1
1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1
1 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 1
1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1
1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1
1 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1
1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1
1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1
1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1
1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 1
1 1 0 0 1 0 0 4 0 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 1
1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1
1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 1 0 1
1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1
1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1
1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1
1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 1
1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1
1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/
