| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 697 人关注过本帖
标题:acm中c++的三道题目
只看楼主 加入收藏
zhl_881213
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2009-8-26
结帖率:0
收藏
已结贴  问题点数:20 回复次数:2 
acm中c++的三道题目
此三题我不会做 不知道如何入手 希望各位可以帮帮我~
如果解答后可以短信我或者直接发上来都可~麻烦了!
c++.rar (15.81 KB)
搜索更多相关主题的帖子: acm 
2009-08-28 19:57
xufen340
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:166
专家分:1351
注 册:2009-8-7
收藏
得分:10 
第三题:   有一个铺着正方形地砖的长方形房间。每个瓷砖不是被涂了红色就是被涂了黑色。一个人正站在一块黑色的瓷砖上。从一个瓷砖上,他可以移动到四块临近的瓷砖中的任一个上。但是他不能走到红色的瓷砖上去,只能走黑的。
    写一个程序吧~来计算出他重复上边的规则可以到达的黑色瓷砖的数目。
解答:
考虑步骤:
人在什么地方按什么规矩怎么走。
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;
}




2009-08-30 13:52
平凡不在
Rank: 2
等 级:论坛游民
帖 子:39
专家分:69
注 册:2009-8-7
收藏
得分:10 
回复一楼:
    你能不能把题目解释的更清楚些呀?谢谢!!!!!!!!!
2009-08-30 22:23
快速回复:acm中c++的三道题目
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030784 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved