首页 > ACM题库 > HDU-杭电 > HDU 1172 猜数字-BFS-[解题报告] C++
2013
12-03

HDU 1172 猜数字-BFS-[解题报告] C++

猜数字

问题描述 :

猜数字游戏是gameboy最喜欢的游戏之一。游戏的规则是这样的:计算机随机产生一个四位数,然后玩家猜这个四位数是什么。每猜一个数,计算机都会告诉玩家猜对几个数字,其中有几个数字在正确的位置上。
比如计算机随机产生的数字为1122。如果玩家猜1234,因为1,2这两个数字同时存在于这两个数中,而且1在这两个数中的位置是相同的,所以计算机会告诉玩家猜对了2个数字,其中一个在正确的位置。如果玩家猜1111,那么计算机会告诉他猜对2个数字,有2个在正确的位置。
现在给你一段gameboy与计算机的对话过程,你的任务是根据这段对话确定这个四位数是什么。

输入:

输入数据有多组。每组的第一行为一个正整数N(1<=N<=100),表示在这段对话中共有N次问答。在接下来的N行中,每行三个整数A,B,C。gameboy猜这个四位数为A,然后计算机回答猜对了B个数字,其中C个在正确的位置上。当N=0时,输入数据结束。

输出:

每组输入数据对应一行输出。如果根据这段对话能确定这个四位数,则输出这个四位数,若不能,则输出"Not sure"。

样例输入:

6
4815 2 1
5716 1 0
7842 1 0
4901 0 0
8585 3 3
8555 3 2
2
4815 0 0
2999 3 3
0

样例输出:

3585
Not sure

连连看

要求:

如果某两个相同的棋子,可以通过一条线连起来(这条线不能经过其它棋子),而且线的转折次数不超过两次,那么这两个棋子就可以在棋盘上消去。注意:连线不能从外围绕过。0表示没有棋子

还是老毛病,没看清题就开始做了,一直WA,上网看了别人的代码,发现有条件f[x][y]==0

才注意到,0表示没有棋子,连线只能通过没有棋子的地方连线。其他思路跟hdu1728 逃离迷宫思路差不多,都是要考虑转弯数,不能对点进行标记,并且从起点到终点要找最小的转弯数存入a[x][y],这样对于每个进队出队的点的转弯数都小于题目要求的最大转弯数,提高了效率,这题与逃离迷宫不同点在于判定条件都是在f[x][y]==0下进行连线的,所以每一个进队的点都必须满足(f[x][y]=0||(x==cx&&y==cy))

额,代码太弱了,1250MS……

以后一定要改掉这个不细心的毛病……

#include<stdio.h>
 #include<string.h>
 #include<queue>
 using namespace std;
 int a[1005][1005],f[1005][1005];
 struct node
 {
     int x,y;
     int flag;
     int count;
 };
 int n,m;
 int d[4][2]={0,1,0,-1,1,0,-1,0};
 int judge(int x,int y)
 {
     if(x>=1&&x<=n&&y>=1&&y<=m)
         return 1;
     return 0;
 }
 int bfs(int x,int y,int cx,int cy)
 {
     int i;
     queue<node>q;
     node cur,next;
     cur.x=x;
     cur.y=y;
     cur.flag=-1;
     cur.count=0;
     q.push(cur);
     a[x][y]=0;
     while(!q.empty())
     {
         cur=q.front();
         q.pop();
         if(cur.count>2)
         return 0;
         for(i=0;i<4;i++)
         {
             next.x=cur.x+d[i][0];
             next.y=cur.y+d[i][1];
             if(judge(next.x,next.y))
             {
                 if(cur.flag==-1||i==cur.flag)
                 {
                     next.flag=i;
                     next.count=cur.count;
                 }
                 if(cur.flag!=-1&&i!=cur.flag)
                 {
                     next.flag=i;
                     next.count=cur.count+1;
                 }
                 
                 if((a[next.x][next.y]>=next.count)&&(next.count<=2))
                 {    
                     if(f[next.x][next.y]==0||next.x==cx&&next.y==cy)
                     {
                         a[next.x][next.y]=next.count;
                         if(next.x==cx&&next.y==cy)
                             return 1;
                         
                         q.push(next);
                     }
                 }
             }
         }
     }
     return 0;
 }
 int main()
 {
     int i,j,sx,sy,cx,cy;
     int t;
     while(scanf("%d%d",&n,&m),n!=0||m!=0)
     {
         for(i=1;i<=n;i++)
             for(j=1;j<=m;j++)
             {
                 scanf("%d",&f[i][j]);
             }
             scanf("%d",&t);
             for(i=1;i<=t;i++)
             {
                 scanf("%d%d%d%d",&sx,&sy,&cx,&cy);
                 if(f[sx][sy]!=f[cx][cy]||f[sx][sy]==0||f[cx][cy]==0||(sx==cx&&sy==cy))
                 {
                     printf("NO\n");
                     continue;
                 }
                 else
                 {
                     memset(a,9,sizeof(a));
                     if(bfs(sx,sy,cx,cy))
                         printf("YES\n");
                     else
                         printf("NO\n");
                 }
             }
     }
     return 0;
 }

 

 


,
  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count