|
#2
xufen3402009-08-30 13:52
第三题： 有一个铺着正方形地砖的长方形房间。每个瓷砖不是被涂了红色就是被涂了黑色。一个人正站在一块黑色的瓷砖上。从一个瓷砖上，他可以移动到四块临近的瓷砖中的任一个上。但是他不能走到红色的瓷砖上去，只能走黑的。
写一个程序吧~来计算出他重复上边的规则可以到达的黑色瓷砖的数目。 解答： 考虑步骤： 人在什么地方按什么规矩怎么走。 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; } |
如果解答后可以短信我或者直接发上来都可~麻烦了！
只有本站会员才能查看附件，请 登录
