标题:阴风习习的大楼
只看楼主
追影flying
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2012-6-5
 问题点数:0 回复次数:1 
阴风习习的大楼
佳佳在一个实验室工作,他每天晚上都要一个人工作到很晚很晚,即使他再努力,也不能避免要上厕所的命运。佳佳是个胆小的孩子,黑夜里上厕所却是一件需要胆量的事,所以佳佳想让你帮他计算一下去厕所的路。
实验室所在的大楼的地形是一个n*n的正方形,每个点或者有路,或者是墙。 这里有一些地方是比较可怕的(比如会有呜呜的风声,或者那里没有灯光),每一个这种地方有一个可怕值k,佳佳经过这里的时候会在心里留下k的阴影。佳佳有一个心理承受能力s,当累计的k值超过或等于s时,佳佳会落荒而逃奔回实验室……现在请你帮佳佳看看,他能不能安全到达厕所呢~实验室在地图的左上角,而厕所在地图的右下角。
要求:
(1)输入:多组测试数据;每组数据输入的第一行是两个数n,s(n<=10,s<=10^9);接下来n行,每行有n个数,分别代表:0 这个位置是空地(实验室和厕所都是0),-1 这个位置是墙,其他正整数:这个位置的可怕程度。
(2)输出:对于每组数据,输出Yes表示佳佳能安全到达厕所,否则输出No。
(3)所设计的数据结构应尽可能节省存储空间。
(4)程序的运行时间应尽可能少  
谁能帮我做这一题啊  求帮助  我急用
搜索更多相关主题的帖子: 正方形 佳佳 能力 
2012-06-06 19:53
追影flying
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2012-6-5
得分:0 
#include "iostream.h"
#include "queue"
using namespace std;
struct nod{
    int x,y,val;
    bool friend operator < (nod a, nod b)
    {     
        return a.val > b.val;
   }
}head;
    priority_queue<nod> que;//优先队列,大的优先
    int dir[4][2]={-1,0,0,1,1,0,0,-1},n,s, map[11][11];
    bool bfs()
    {   
        nod temp, te;//nod型临时结点
        int i ,min = 110000000;
        while(!que.empty())//队列中还有要处理的点
        {      
            temp = que.top();
            que.pop();
            if(temp.x == n-1 && temp.y == n-1)
            {  if(min > temp.val)
            min = temp.val;  
            continue;
 }      
            for(i = 0; i < 4; i++)
            {
                te.x = temp.x + dir[i][0];
                te.y = temp.y + dir[i][1];
                if(te.x >=0 && te.y >= 0 && te.x < n && te.y < n && map[te.x][te.y] != -1)
                { te.val = temp.val + map[te.x][te.y];  
                que.push(te);
                map[te.x][te.y] = -1;
 }  
      }
    }   
        if(min >= s)
            return 0;
        else return 1;
}
    int main()
    {   
        int i,j;
        while(scanf("%d%d",&n,&s)!=EOF)
        {   while(!que.empty()) que.pop();
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)  
                scanf("%d",&map[i][j]);
            map[0][0] = -1;  
            head.x = head.y = head.val= 0;
            que.push(head);
            printf(bfs()?"Yes\n":"No\n");
    }   
        return 0;
    }

 大神们帮忙看看这段代码,给代码后面加上注释,,谢谢啦
2012-06-10 14:04



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-370959-1-1.html




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

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