首页 > 搜索 > BFS搜索 > hdu 2351 One is an Interesting Number-BFS-[解题报告]C++
2014
01-05

hdu 2351 One is an Interesting Number-BFS-[解题报告]C++

One is an Interesting Number

问题描述 :

Numbers are interesting, but some are inherently more interesting than others, by various criteria. Given a collection of numbers, you are to find the
most interesting ones.

A number X is more interesting than another number Y if it has more attributes than Y. For the purposes of this problem, the attributes that are
interesting are:

Note that 0 has no multiples other than itself, and 1 is not prime.

In addition to the above attributes, there are also those which depend on the other numbers in a given collection:

This makes for a total of thirteen possible attributes. Note that meeting the criteria for a particular attribute in multiple ways (1 is the factor of all
other numbers, for example) still only counts as a single instance of an attribute.

Given a collection of numbers, you are to determine which numbers in that collection are most interesting.

输入:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer M (1 ≤ M ≤ 100) indicating how many numbers are in the collection;
A series of M lines, each with a single integer X (1 ≤ X ≤ 1000000). There will be no duplicate integers X within the same data set.

输出:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of
the following components:

A line containing a single integer M (1 ≤ M ≤ 100) indicating how many numbers are in the collection;
A series of M lines, each with a single integer X (1 ≤ X ≤ 1000000). There will be no duplicate integers X within the same data set.

样例输入:

2
2
1
100
3
2
3
4

样例输出:

DATA SET #1
1
DATA SET #2
4

不得不说这道题木让人很蛋疼,本来是一道很简单的广搜题目,但是由于人的位置处于一块连续的区域,所以难度就出来了,关键是防守人的位置怎么存储,这里我是把它存储在一个node类型的vector数组里面,为什么用vector呢,因为之前总是莫名其妙的MLE,不过到后来证明用数组也是不超内存的,应该是我的程序进入了死循环。

#include<iostream>
 #include<string.h>
 #include<string>
 #include<stdio.h>
 #include<queue>
 #include<vector>
 using namespace std;
 char Map[101][101];
 int mark[101][101];//设置走过的图的标志数组
 int H,W;
 struct node
 {
     int x,y;//点的坐标x,y
 };
 struct Node
 {
     vector<node>dep;//存放防守人的区域(由node点构成)
     int depth;//描述位置的深度
 };
 int X[4]={1,-1,0,0};//X,Y数组表示方向
 int Y[4]={0,0,1,-1};
 int  Check(int dirX,int dirY,Node N)
 {
     int i,len=N.dep.size(),state=0;//state表示check的状态
     int newx,newy;
     newx=N.dep[0].x+dirX;
     newy=N.dep[0].y+dirY;
     if(mark[newx][newy]==1) return 0;//表不可以移动
     for(i=0;i<len;i++)
     {
         newx=N.dep[i].x+dirX;
         newy=N.dep[i].y+dirY;
         if(newx<0 || newx>=H || newy<0 || newy>=W)return 0;//不可以新的newx newy不在图的范围内,所以不可以移动
         if(Map[newx][newy]=='O')
         {
             return 0;
         }
         if(Map[newx][newy]=='Q')state=1;//表示新移动到的位置可以catch him
     }
     if(state)return 1;//表示抓到四号位,进入这条语句说明新位置没有碰到O,即前锋
     return 2;//表示可以移动到新位置
 }
 int BFS(Node N)
 {
     queue<Node>q;
    int i=0,j=0,len;
    Node N1;
     mark[N.dep[0].x][N.dep[0].y]=1;//先将N的位置标志访问过
    q.push(N);//进队
    while(!q.empty())
    {
       N1=q.front();
       for(i=0;i<4;i++)
       {
           int state=Check(X[i],Y[i],N1);//对每一个方向进行检查可不可以进行移动,或是catch him
           if(state==0)continue;//不可以移动
           if(state==1)return N1.depth+1;//catch him 返回当前位置深度再加1
           if(state==2)//可以进行移动
           {
                Node N2;
                 node n;
                 len=N1.dep.size();
                 for(j=0;j<len;j++)//对当前位置内所有点全部进行X[i],Y[i]方向移动
                 {
                     n.x=(N1.dep[j]).x+X[i];
                     n.y=(N1.dep[j]).y+Y[i];
                     N2.dep.push_back(n);
                 }
                 N2.depth=N1.depth+1;//更新深度
                  mark[N2.dep[0].x][N2.dep[0].y]=1;//泥马呀,就是这句标志位移动到了下面注释的那条,就出现了各种错误,上不起啊
                 q.push(N2);
           }
       }
        //mark[N1.dep[0].x][N1.dep[0].y]=1;
       q.pop();
    }
    return 0;
 }
 int main()
 {
     int i,j,ans;
     while(scanf("%d %d",&H,&W)!=EOF)
     {
         if(H==0 && W==0)break;
         memset(mark,0,sizeof(mark));
         node n;
         Node N;
         N.depth=0;
         for(i=0;i<H;i++)
         {
             getchar();//读取换行符
             for(j=0;j<W;j++)
             {
                 scanf("%c",&Map[i][j]);
                 if(Map[i][j]=='D')
                 {
                     n.x=i;
                     n.y=j;
                     N.dep.push_back(n);
                 }
             }
         }
         //mark[N.dep[0].x][N.dep[0].y]=1;
         ans=BFS(N);
         if(ans)
         {
             printf("%d\n",ans);continue;
         }
         puts("Impossible");
     }
     return 0;
 }

解题转自:http://www.cnblogs.com/lonelycatcher/archive/2011/09/23/2186707.html


,
  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥