一个DFS(深搜)的简单题目:
 
大概题意:就是给定一个m*n的矩阵,有很多的空间,有的是由墙隔开的,现在要找到一共有多少个
房间,以及最大的房间是多大?并把它两打印出来。
具体思路:
第一:定义一个存储矩阵数据date的二维数组,以及用来做标记的tmp二维数组和一个用
来存储东南西北四个方向能否通行的二维结构体数组;
第二:西是1,北是2,东是4,南是8,因此要判断是否能通过,只要对date中的数据依次
和1,2,4,8相与,就知道了是否能过通行。
第三:就是一个深搜,也就是我们所说的完美的递归调用。具体代码实现如下:
 
Result                            Memory                         Time                  Code Length
Accepted                         224k                              0MS                   1546B
 

#include<stdio.h>
#define DEN 51

struct DIR
{
         int east,south,west,north;
}mark[DEN][DEN];      //定义一个结构体,用来存储东南西北是否能通过

int tmp[DEN][DEN];    //用来做标记的,看是否已经走过
int date[DEN][DEN];   //用来来存储输入的数据部分
int m,n,max;          //max用来存储最大值
int t;                //t用来计数
void sign()          //调用sign函数,用来计算东西南北四个方向能否通过
{
         int i,j;
         for(i=0;i<m;i++)
               for(j=0;j<n;j++)
               {
                      if(!(date[i][j]&1))
                              mark[i][j].west=1;//西能通过
                      if(!(date[i][j]&2))
                              mark[i][j].north=1;//北能通过
                      if(!(date[i][j]&4))
                              mark[i][j].east=1;//东能通过
                      if(!(date[i][j]&8))
                              mark[i][j].south=1;//南能通过
               }
}

void find(int i,int j)  //用find来查找连通房间
{
          if(t>max)
          max=t;
          if(mark[i][j].east==1&&tmp[i][j+1]==0)  //如果东边不是墙,并且东边的一个房间没有标记,就进入。
          {
                   tmp[i][j+1]=1;      //进入之后马上标记为已走过哦         
                   t++;                //总房间个数加一
                  find(i,j+1);        //然后进入
          }
         if(mark[i][j].south==1&&tmp[i+1][j]==0)  //同理
         {
                 tmp[i+1][j]=1;
                 t++;
                 find(i+1,j);
         }
        if(mark[i][j].west==1&&tmp[i][j-1]==0)   //同理
        {
                 tmp[i][j-1]=1;
                 t++;
                 find(i,j-1);
         }
         if(mark[i][j].north==1&&tmp[i-1][j]==0)  //同理
         {
                 tmp[i-1][j]=1;
                 t++;
                 find(i-1,j);
         }
         return ;

}

int main()
{
         int i,j,k=0;
         scanf("%d%d",&m,&n);
         for(i=0;i<m;i++)
                 for(j=0;j<n;j++)
                        scanf("%d",&date[i][j]);
         sign();          
         for(i=0;i<m;i++)
                for(j=0;j<n;j++)
               {
                       if(!tmp[i][j])  //未被标记才能进入
                       {
                             t=1;  //一进入t就应该为1了哦
                             tmp[i][j]=1;
                             find(i,j);
                             k++;   //每能调用一次,就证明一定有一个房间哦,所以要加一
                       }
               }
        printf("%d\n%d\n",k,max);//输出结果
        return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation