首页 > 代码库 > tyvj1117 拯救ice-cream
tyvj1117 拯救ice-cream
背景
天好热……Tina顶着那炎炎的烈日，向Ice-cream home走去……
可是……停电了……
冰淇淋们躺在Ice-cream home的冰柜里，慢慢地……慢慢地……融化…………
你说，她能赶在冰淇淋融化完之前赶到Ice-cream home去吗？
可是……停电了……
冰淇淋们躺在Ice-cream home的冰柜里，慢慢地……慢慢地……融化…………
你说，她能赶在冰淇淋融化完之前赶到Ice-cream home去吗？
描述
给你一张坐标图，s为Tina的初始位置，m为Ice-cream home的位置，‘.’为路面，Tina在上面，每单位时间可以移动一格；‘#’为草地，Tina在上面，每两单位时间可以移动一格（建议不要模仿—毕竟Tina还小）；‘o’是障碍物，Tina不能在它上面行动。也就是说，Tina只能在路面或草地上行走，必须绕过障碍物，并到达冰淇淋店。但是…………不保证到达时，冰淇淋还未融化，所以……就请聪明的你……选择最佳的方案啦…………如果，Tina到的时候，冰淇淋已经融化完了，那她可是会哭的。
输入格式
依次输入冰淇淋的融化时间t(0<t<1000)，坐标图的长x,宽y(5<=x,y<=25){太长打起来好累……}，和整张坐标图。
输出格式
判断按照最优方案是否可以赶在冰淇淋融化之前到达冰淇淋店（注：当T=最优方案所用时间，则判断为未赶到），如赶到，输出所用时间；如未赶到，输出Tina的哭声——“55555”（不包括引号）。
测试样例1
输入
11
10
8
......s...
..........
#ooooooo.o
#.........
#.........
#.........
#.....m...
#.........
输出
10
思路：
普通广搜+优先队列
代码：
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<queue>using namespace std;struct node{ int x; int y; int dist; friend bool operator < (node a,node b){ return a.dist > b.dist; }};priority_queue<node> q;int t,x,y,startx,starty,endx,endy,map[50][50],jud[50][50];int dx[4] = {-1,0,1,0};int dy[4] = {0,-1,0,1};void input(){ cin>>t>>x>>y; char cmd; for(int i = 1;i <= y;i++){ for(int j = 1;j <= x;j++){ cin>>cmd; if(cmd == ‘.‘) map[i][j] = 1; if(cmd == ‘#‘) map[i][j] = 2; if(cmd == ‘o‘) map[i][j] = 3; if(cmd == ‘s‘){ map[i][j] = 1; startx = j; starty = i; } if(cmd == ‘m‘){ map[i][j] = 1; endx = j; endy = i; } } } node tmp; tmp.x = startx; tmp.y = starty; tmp.dist = 0; q.push(tmp); for(int i = 1;i <= 40;i++){ for(int j = 1;j <= 40;j++){ jud[i][j] = 100000000; } }}bool bfs(){ node now,next; int nx,ny; while(!q.empty()){ now = q.top(); q.pop(); for(int i = 0;i < 4;i++){ nx = now.x + dx[i]; ny = now.y + dy[i]; if(nx < 1 || nx > x || ny < 1 || ny > y || map[ny][nx] == 3 ||jud[ny][nx] <= now.dist + map[ny][nx]) continue; next.x = nx; next.y = ny; next.dist = now.dist + map[ny][nx]; if(nx == endx && ny == endy){ if(next.dist >= t) return false; else{ cout<<next.dist<<endl; return true; } } q.push(next); jud[ny][nx] = next.dist; } }}int main(){ input(); if(!bfs()) cout<<55555<<endl; return 0;}
tyvj1117 拯救ice-cream
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。