Robot lifts heavy objects
Title Description
The Robotic Mobility Institute (RMI) is now experimenting with robots to move objects. The shape of the robot is a diameter\(1.6\) meter ball. In the pilot phase, the robot was used to move goods in a storage room. The storage room was a\(N\times M\) of the grid, with some grids being immovable obstacles. The center of the robot is always on the grid points and, of course, the robot must carry the item to the designated place in the shortest possible time. The robot receives commands such as:
- forward motion\(1\) Steps (
Creep）； - forward motion\(2\) Steps (
Walk）； - forward motion\(3\) Steps (
Run）； - Turn left (
Left）； - Turn right (
Right）。
The time required for each instruction is\(1\) Seconds. Please calculate the minimum time required for the robot to complete the task.
input format
The first row is two positive integers\(N,M\ (1\le N,M\le50)\)below\(N\) The rows are the construction of the pantry.\(0\) Indicating accessibility.\(1\) Indicates an obstacle, with a space separating the numbers. The next line has\(4\) integer sum (math.)\(1\) The capital letters are the rows and columns of the grid in the upper-left corner of the start and target points, respectively, and the facing direction at the start (east).\(\tt E\)south\(\tt S\)Spanish\(\tt W\)North\(\tt N\)), numbers are separated from each other, and numbers are separated from letters by a single space. The facing direction of the endpoints is arbitrary.
output format
An integer indicating the minimum time required for the robot to complete the task. If it is not reachable, output\(-1\)。
Sample #1
Sample Input #1
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
Sample Output #1
12
This question is a pretty typical dfs question, but there are a lot of pitfalls that have pitted me many times in a row 。。。。 No hee hee
- The first thing is to calculate the steering time, I will NSWE is a direction algebra as 1, 2, 3, 4, and then take the absolute value of their difference, representing the steering time, but did not notice that 4 and 1 difference of 3, but in fact only 1 second, this error is purely guilty.... I wrote it too fast.
- Then there's the question of how to convert the input box plot into a grid point plot, which has to be plotted
- After that it's possible for the robot to jump over obstacles when it takes three steps, but that's not allowed, so it needs to be pruned
- The last thing is to use the priority queue to take out the node with the smallest tm in the first place
- Then there are the toxic points of its test cases, such as the starting point stuck in the wall (@-@.)!
The details are in the code
Code:
#include<iostream>
#include<cstdio>;
#include<cstring>
#include<algorithm>.
#include<string>.
#include<queue> #include<cstring> #include<algorithm>
#include<cmath> #include<i
#include<iomanip> #include<queue> #include<cmath>
using namespace std.
int a[55][55]; //store the box plot
long long mp[55][55]; //store the plot of the grid points, i.e. the plot of the robot's walks
int dis[55][55]; //Used to record the shortest time the robot has traveled to that grid point
int n, m; //Size of the square grid
int x1, y11, x2, y2; //record the coordinates of the starting and ending points
int sto;//direction of the start point
string ch; //read the direction of the starting point
struct node
int x; //Read the direction of the starting point.
int x; //Coordinates of the current point
int y;//coordinates of current point
int to;//1=>N(up) 2=>E(right) 3=>S(down) 4=>W(left) direction number
int tm;// shortest time from start point to current point
bool operator < (node a)const {
return tm > ;
}
// The priority queue in stl prioritizes taking out the maximum value by default, so overload the operator to ensure that the least costly element is taken out each time
};
priority_queue<node> que; // priority queue
node now, nxt;
int dx[] = { 0, -1,0,1,0 };
int dy[] = { 0, 0,1,0,-1 };
int abs(int a, int b) {
return a > b ? a - b : b - a; }
}
int calchange(int now, int aft) {
// Note this case
if (abs(now, aft) == 3) {
return 1; }
}
else {
return abs(now, aft); } else {
}
}
void readto()
} void readto()
switch (ch[0])
{
case 'N': sto = 1; break;
case 'S': sto = 3; break;
case 'E': sto = 2; break;
break; case 'E': sto = 2; break; }
break; }
}
void change()
{
// Set the borders all to 1, because the robot has a width and can't appear there
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (a[i][j] == 1)// If the current frame is an obstacle, none of its four vertices can go
{
mp[i + 1][j] = 1;
mp[i][j + 1] = 1;
mp[i + 1][j + 1] = 1;
mp[i][j] = 1;
}
if (i == 1 || j == 1) {
mp[i][j] = 1; }
}
if (i == n || j == m) {
mp[i + 1][j + 1] = 1; }
}
}
}
mp[n + 1][1] = 1;
mp[1][m + 1] = 1; }
}
void bfs() {
dis[x1+1][y11+1] = 0;
node fir.
= x1+1.
= y11+1.
= sto.
= 0;
(fir);
int changecost = 0;
while (! ()) {
now = ();
//This is the code that prints the path
//cout << << " " << << " " << << " " << << endl;
if ( == x2+1 && == y2+1) break; // prune
();
if ( > dis[][]) continue; //pruning, this can't be added, seems useless
// Traverse the four directions
for (int i = 1; i <= 4; i++) {
changecost = calchange(, i); //Three ways to move.
//Three ways to move
for (int j = 1; j <= 3; j++) {
= + dx[i] * j.
= + dy[i] * j;
//if (mp[][] == 1 && j==1 || mp[][] == 1 && j == 2) break;
if ( <= 1 | | > n | | <= 1 | | > m | | mp[][] == 1) break; // pruning, this boundary judgment is best done against the graph
= i;
= + 1 + changecost;
if (dis[][] > ) {
dis[][] = ;
(nxt);
}
}
}
}
}
int main()
{
memset(dis, 1061109567, sizeof(dis));
cin >> n >> m;
for (int i = 1; i <= n; ++i)
m; for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
m; for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i][j]);
}
}
cin >> x1 >> y11 >> x2 >> y2; // in c++ y1 is a function, so change it
cin >> ch.
readto();// determine the direction represented by ch
change();//convert the grid map to a map of grid points that the robot can walk on
//The special judgment, to prevent dependence on the wall, or the end of the wall, the starting point and the end of the index is best against the map
if (mp[x1 + 1][y11 + 1] == 1 || mp[x2+1][y2+1]==1) {
cout << -1.
return 0;
}
bfs();
// This is the code to print the lattice plot, so you can print it out and see it
/*for (int i = 1; i <= n + 1; i++) {
for (int j = 1; j <= m + 1; j++) {
cout << mp[i][j] << " ";;
}
cout << endl;
}*/
if (dis[x2+1][y2+1] == 1061109567) {
cout << -1;
}
else {
cout << dis[x2 + 1][y2 + 1];
}
}