1321. Robot
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
Karell Incorporated has designed a new exploration robot that has the ability to explore new terrains, this new robot can move in all kinds of terrain, it only needs more fuel to move in rough terrains, and less fuel in plain terrains. The only problem this robot has is that it can only move orthogonally, the robot can only move to the grids that are at the North, East, South or West of its position.
The Karell`s robot can communicate to a satellite dish to have a picture of the terrain that is going to explore, so it can select the best route to the ending point, The robot always choose the path that needs the minimum fuel to complete its exploration, however the scientist that are experimenting with the robot, need a program that computes the path that would need the minimum amount of fuel. The maximum amount of fuel that the robot can handle is 9999 units
The Terrain that the robot receives from the satellite is divided into a grid, where each cell of the grid is assigned to the amount of fuel the robot would need to pass thought that cell. The robot also receives the starting and ending coordinates of the exploration area.
Input
The first line of the input file is the number of tests that must be examined.
The first line of the test is the number of rows and columns that the grid will contain. The rows and columns will be <!-- MATH $0 < row \le 100$ -->0 < row100 <TEX2HTML_VERBATIM_MARK>, <!-- MATH $0 < column \le 100$ -->0 < column100 <TEX2HTML_VERBATIM_MARK>
The next lines are the data of the terrain grid
The last line of the test has the starting and ending coordinates.
Output
One line, for each test will have the amount of fuel needed by the robot
Sample Input
3 5 5 1 1 5 3 2 4 1 4 2 6 3 1 1 3 3 5 2 3 1 2 2 1 1 1 1 1 1 5 5 5 4 2 2 15 1 5 1 15 1 5 3 10 1 5 2 1 1 8 13 2 15 1 1 1 4 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 10
Sample Output
10
这又是一道典型的寻找最短路径的题目。题目没有很大的难度,注意一下算法的实现就行了。
这题目图的存储在矩阵中,一次遍历,寻找就可以找到最短路径。
题目链接: http://soj.me/1321
参考代码:
#include <iostream> #include <stdio.h> #include <string> #include <cstring> #include <queue> #include <set> #include <vector> using namespace std; int dis[109][109]; struct Gra { int r; int c; friend bool operator <(Gra g1, Gra g2) { if(dis[g1.r][g1.c] < dis[g2.r][g2.c]) return true; } }; int main() { int t; cin >> t; while (t --) { int a, b; scanf("%d%d", &a, &b); int s[109][109]; for (int i = 1; i <= a; ++ i) { for (int j = 1; j <= b; ++ j) { cin >> s[i][j]; } } int ar, ac, br, bc; cin >> ar >> ac >> br >> bc; set<Gra> q; int know[109][109]; memset(know, 0, sizeof(know)); memset(dis, 9999999, sizeof(dis)); Gra tu[10009]; tu[1].r = ar; tu[1].c = ac; q.insert(tu[1]); Gra temp; int i = 2; //know[ar][ac] = 1; dis[ar][ac] = s[ar][ac]; set<Gra>::iterator it; set<Gra>::iterator itt; while (!q.empty()) { it = q.begin(); temp = *it; itt = it; ++ it; Gra tem; for (; it != q.end(); ++ it) { tem = *it; if (dis[temp.r][temp.c] > dis[tem.r][tem.c]) { temp = tem; itt = it; } } q.erase(itt); know[temp.r][temp.c] = 1; if (temp.r == br && temp.c == bc) { cout << dis[temp.r][temp.c] << endl; break; } if (temp.c - 1 >= 1) { tu[i].c = temp.c - 1; tu[i].r = temp.r; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } if (temp.r - 1 >= 1) { tu[i].r = temp.r - 1; tu[i].c = temp.c; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } if (temp.c + 1 <= b) { tu[i].c = temp.c + 1; tu[i].r = temp.r; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } if (temp.r + 1 <= a) { tu[i].r = temp.r + 1; tu[i].c = temp.c; if (know[tu[i].r][tu[i].c] == 0) { if (dis[tu[i].r][tu[i].c] > dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]) { dis[tu[i].r][tu[i].c] = dis[temp.r][temp.c] + s[tu[i].r][tu[i].c]; q.insert(tu[i]); ++ i; } } } } } //system("pause"); }
相关推荐
sicily 1562_LVM.cpp参考代码
中山大学 ACM sicily 1294 题目代码
sicily 1274的AC源码,通过且速度快,适合学生使用
本程序解决了Sicily平台上Queue的问题,有较好的可读性
本程序是中山大学sicily-1137-1145-1146-1147-1154-1157-1194的代码
这是C++解题常用的模板,对参加C++机试有较大帮助
西西里全部练习输入输出以及标准程序 超高精度浮点数的输出问题 关联数组
sicily 1817和1818的程序,各有两种方法,供参考。
本程序是中山大学sicily 1004-1007-1010-1014-1021 参考代码
本程序是中山大学sicily上1200-1221-1298-1324-1325的参考代码。
1005. 有向图边的分类 12图算法例题1000. sicily 1155. Can I Post the letteTime Limit: 1sec Mem
包括 sicily online judge 1149等部分题目,线性表,最小生成树,中缀转后缀并计算后缀表达式等。
sicily部分源代码,全都亲测,可通过
中大sicily online judge的刷题指南,里面介绍得很详细,不过,最近sicily好像不能外网访问了。
sicily(soj) 1022 1064 1310 1740 1876 1934 六题的源代码(数据结构综合应用题)
本cpp是sicily的1006的解题代码 这份代码以最简单的方式实现了它的功能要求 值得学习一番
112页的大礼包,sicily的部分ac代码。
Sicily的题目分类:各种题目的分类,大致方法,以及题目难度规范
sicily1007题答案,附代码解释,可以在平台上通过