|
#2
追影flying2012-06-10 14:04
#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; } 大神们帮忙看看这段代码，给代码后面加上注释，，谢谢啦 |
佳佳在一个实验室工作，他每天晚上都要一个人工作到很晚很晚，即使他再努力，也不能避免要上厕所的命运。佳佳是个胆小的孩子，黑夜里上厕所却是一件需要胆量的事，所以佳佳想让你帮他计算一下去厕所的路。
实验室所在的大楼的地形是一个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）程序的运行时间应尽可能少
谁能帮我做这一题啊 求帮助 我急用