c++.rar
第三题： 有一个铺着正方形地砖的长方形房间。每个瓷砖不是被涂了红色就是被涂了黑色。一个人正站在一块黑色的瓷砖上。从一个瓷砖上，他可以移动到四块临近的瓷砖中的任一个上。但是他不能走到红色的瓷砖上去，只能走黑的。
写一个程序吧~来计算出他重复上边的规则可以到达的黑色瓷砖的数目。
解答：
考虑步骤：
人在什么地方按什么规矩怎么走。
1.首先，地方：长方形的有2种颜色，考虑长方形房间地砖用数组来表示，在程序里因为方便，我就把数组固定为6*9大小，，0，1分别表示不同颜色，1为黑色，我不再编写输入数组的过程，另外为了考虑最复杂性，我把整个房间都弄了个黑色，摄影暗房吧，你可以改变成0。数据结构中的数组。
2.其次，规矩：地砖到到地砖能连通就可以走。这个问题概括为只要两个点有连接，从一个点走到另一个点，那么问题解答已经呼之欲出了，是个图形问题。数组的二维对应点的坐标，我找到坐标，从数组中就能找到颜色。然后通过数组周围颜色，我按上右下左的方位得到黑色，我就再转化成坐标，就可以前进了。数据结构中的图的领接列表，顶点的上右下左哪个是黑色的，哪个就是顶点的领接节点。
3.最后：怎么走，从一个点出发，顺时针根据原则（领接列表），走遍周围，以一个顶点为例，假如上面右面是黑色，那就先走到上面，再回到顶点，再走到右面，再回到顶点。这种走法在数据结构中叫广度优先法。我下面写的就是广度优先法，当然也可以是深度优先，随便你。
下面是我写的例子：
#include<iostream>
using namespace std;
//地板石砖，全为黑色。6*9大小
int ground[6][9]={
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,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,
};
//声明石砖顶点结构，ni,nj为相对数组位置。
struct node
{
int ni;
int nj;
struct node *next;
};
//6*9的石砖共有54块，每块都作为一个顶点。
node Head[54];
/*建立领接列表，每个顶点的领接顶点按上，右，下，下排列。*/
void linknearnode(int posi,int posj);
//显示领接列表
void shownearnode(node Head[]);
//广度优先遍历整个图,返回路径.(ni,nj)为起始顶点坐标.
node* BFS(int ni,int nj);
int main()
{
int i,j;
node* pbfs;
int ncount=0;
//顶点数组初始化
for(i=0;i<54;i++){
Head[i].ni=i/9;
Head[i].nj=i%9;
Head[i].next=NULL;
}
//建立领接列表
for(i=0;i<9;i++)
for(j=0;j<9;j++){
linknearnode(i,j);
}
shownearnode(Head);
//建立广度优先链表
pbfs=BFS(0,0);
//输出广度优先链表
while(pbfs!=NULL){
cout<<"("<<pbfs->ni<<","<<pbfs->nj<<")"<<endl;
pbfs=pbfs->next;
ncount++;
}
cout<<endl<<ncount<<endl;
return 0;
}
void linknearnode(int posi,int posj)
{
node* nearnode; //领接列表的顶点
node* pointer;
/*如果上面有石砖，那再判断是不是黑色，黑色增加对映顶点的领接顶点*/
if(posi>0){
if(ground[posi-1][posj]==1){
nearnode=(node*)malloc(sizeof(node));
nearnode->ni=posi-1;
nearnode->nj=posj;
nearnode->next=NULL;
pointer=&(Head[posi*9+posj]);
while(pointer->next!=NULL)
pointer=pointer->next;
pointer->next=nearnode;
}
}
/*如果右面有石砖，那再判断是不是黑色，黑色增加对映顶点的领接顶点*/
if(posj<9){
if(ground[posi][posj+1]==1){
nearnode=(node*)malloc(sizeof(node));
nearnode->ni=posi;
nearnode->nj=posj+1;
nearnode->next=NULL;
pointer=&(Head[posi*9+posj]);
while(pointer->next!=NULL)
pointer=pointer->next;
pointer->next=nearnode;
}
}
/*如果下面有石砖，那再判断是不是黑色，黑色增加对映顶点的领接顶点*/
if(posi<5){
if(ground[posi+1][posj]==1){
nearnode=(node*)malloc(sizeof(node));
nearnode->ni=posi+1;
nearnode->nj=posj;
nearnode->next=NULL;
pointer=&(Head[posi*9+posj]);
while(pointer->next!=NULL)
pointer=pointer->next;
pointer->next=nearnode;
}
}
/*如果左面有石砖，那再判断是不是黑色，黑色增加对映顶点的领接顶点*/
if(posj>0){
if(ground[posi][posj-1]==1){
nearnode=(node*)malloc(sizeof(node));
nearnode->ni=posi;
nearnode->nj=posj-1;
nearnode->next=NULL;
pointer=&(Head[posi*9+posj]);
while(pointer->next!=NULL)
pointer=pointer->next;
pointer->next=nearnode;
}
}
}
//显示领接列表
void shownearnode(node Head[])
{
int ni;
node* phead=Head;
for(ni=0;ni<54;ni++){
phead=&(Head[ni]);
cout<<"("<<phead->ni<<","<<phead->nj<<")";
while(phead->next!=NULL){
phead=phead->next;
cout<<"->"<<"("<<phead->ni<<","<<phead->nj<<")";
}
cout<<endl;
}
}
//
node* BFS(int ni,int nj)
{
node* p;
node* pnewhead;//广度优先的链表的头指针
node* tmp;//临时节点,用来存放邻接列表的节点.
node* s;//广度优先的链表的遍历指针
node* rear;//广度优先的链表的结尾指针
//访问标记
int visited[6][9];
for(int ni1=0;ni1<6;ni1++)
for(int nj1=0;nj1<9;nj1++)
visited[ni1][nj1]=0;
//p指向列表的起始顶点
p=&(Head[ni*9+nj]);
//起点节点放入广度链表弟一个位置
tmp=(node*)malloc(sizeof(node));
tmp->ni=p->ni;
tmp->nj=p->nj;
tmp->next=NULL;
pnewhead=tmp;
s=tmp;
rear=tmp;
while(s!=NULL){
//取顶点
p=&(Head[s->ni*9+s->nj]);
//标记已经访问过
visited[s->ni][s->nj]=1;
p=p->next;
//对应顶点的菲访问过领接节点插在广度链表中
while(p!=NULL){
if(visited[p->ni][p->nj]==0){
//标记已经访问过
visited[p->ni][p->nj]=1;
tmp=(node*)malloc(sizeof(node));
tmp->ni=p->ni;
tmp->nj=p->nj;
tmp->next=NULL;
rear->next=tmp;
rear=rear->next;
}
p=p->next;
}
//插入领接节点使广度链表增加,每个顶点都要遍历一便.
s=s->next;
}
return pnewhead;
}
