These questions are very helpful to improve the coding ability of Guangsou
P1126 Robot Lifting Heavy Objects
Description of topic
The Robotic Mobility Institute (RMI) is currently experimenting with moving objects with robots. The shape of the robot is a ball with a diameter of 1.61.6 meters. During the trial phase, the robot was used to move goods in a storage room. The storage room is an N×M grid, and some grids are immovable obstacles. The center of the robot is always on the grid. Of course, the robot must move the items to the designated place in the shortest time. The instructions accepted by the robot are: move forward 11 steps (Creep); move forward 2 steps (Walk); move forward 33 steps (Run) code>); turn left (Left); turn right (Right). The time required for each command is 11 seconds. Please calculate the minimum time required for the robot to complete the task.
Input format
The first line is two positive integers N, M (N, M≤50), the next N lines are the structure of the storage room, 00 means no barriers, 11 means barriers, and the numbers are separated by a space. The next line has 44 integers and 11 capital letters, which are the row and column of the grid in the upper left corner of the starting point and the target point respectively, the facing direction at the beginning (East E, South S, West W, North N), and the number and numbers, numbers and letters are separated by a space. The facing direction of the endpoint is arbitrary.
Output format
An integer representing the minimum amount of time the robot needs to complete the task. If unreachable, output ?1?1.
Sample input and output
Enter #1 to copy
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
Output #1 Copy
12
For the least-turn problem, it is essentially the shortest path problem:
Every time you turn left or right, the cost will increase by one unit, and every time you go, you will also increase the cost by one unit. What is the minimum cost from the given starting point to the given end point? How many.
Therefore, we can think of using bfs to solve this problem, and most of the shortest path problems are also solved by bfs.
But the difficulty of answering this question is that there are many details in the question.
This question is not a common shortest path problem, and you can’t find a way to do it directly according to the usual shortest path. You need to make some changes to Guangsou: the fighting arena in Guangsou.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 55;
int brr[N][N], arr[N][N], n, m;
typedef struct st {
int y, x, d, t;
}st;
int ty1, tx1, ty2, tx2, D, ans, f[N][N];
int ay[] = { 0,1,0,-1 }, ax[] = { 1,0,-1,0 };
int fc(int a, int b) {
int k1, k2;
k1 = a + 1;
k2 = a - 1;
if (k1 > 3)
k1 = 0;
if (k2 < 0)
k2 = 3;
if (k1 == b || k2 == b) {
return 0;
}
return 1;
}
void bfs() {
queue<st>q;
f[ty1][tx1] = 0;
for (int i = 0; i < 4; i ++ ) {
for (int j = 1; j <= 3; j ++ ) {
int ty, tx, t;
ty = ty1 + ay[i] * j;
tx = tx1 + ax[i] * j;
t = 0;
if (i != D) {
if (fc(i, D)) {
t + = 1;
}
t + = 1;
}
t + = 1;
if (ty <= 1 || ty > n || tx <= 1 || tx > m)
continue;
if (arr[ty][tx] == 1)
break;
if (t > f[ty][tx])
continue;
f[ty][tx] = t;
q.push({ ty,tx,i,t });
}
}
st s;
while (!q.empty()) {
s = q. front();
q. pop();
for (int i = 0; i < 4; i ++ ) {
for (int j = 1; j <= 3; j ++ ) {
int ty, tx, t;
ty = s.y + ay[i] * j;
tx = s.x + ax[i] * j;
t = s.t;
if (i != s.d) {
if (fc(i, s.d)) {
t + = 1;
}
t + = 1;
}
t + = 1;
if (ty <= 1 || ty > n || tx <= 1 || tx > m)
continue;
if (arr[ty][tx] == 1)
break;
if (t > f[ty][tx])
continue;
f[ty][tx] = t;
q.push({ ty,tx,i,t });
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
scanf("%d", &brr[i][j]);
}
}
/*
* Preprocess arr, because the robot is walking on the grid, so we use a new array
*arr to indicate the space that the robot can walk
*/
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if (brr[i][j] == 1) {
arr[i][j] = 1;
arr[i+1][j] = 1;
arr[i][j+1] = 1;
arr[i+1][j+1] = 1;
}
}
}
for (int i = 1; i <= n + 1; i + + ) {
memset(f[i], 0x3f3f3f3f, sizeof(f[i]));
}
scanf("%d%d%d%d", &ty1, &tx1, &ty2, &tx2);
ty1++;
ty2++;
tx1++;
tx2++;
char ch; getchar();
scanf("%c", &ch);
//Convert direction to digital representation
if (ch == 'S') {
D = 1;
}
else if (ch == 'E') {
D = 0;
}
else if (ch == 'W') {
D = 2;
}
else {
D = 3;
}
bfs();
if (f[ty2][tx2] == 0x3f3f3f3f) {
cout << -1 << endl;
}
else {
cout << f[ty2][tx2] << endl;
}
return 0;
}
P2937 [USACO09JAN]Laserphones S
Description of topic
The cows have a new laser-based system so they can have casual conversations while out in the pasture which is modeled as a W x H grid of points (1 <= W <= 100; 1 <= H <= 100).
The system requires a sort of line-of-sight connectivity in order to sustain communication. The pasture, of course, has rocks and trees that disrupt the communication but the cows have purchased diagonal mirrors (‘/’ and ” below) that deflect the laser beam through a 90 degree turn. Below is a map that illustrates the
problem.
H is 8 and W is 7 for this map. The two communicating cows are notated as ‘C’s; rocks and other blocking elements are notated as ‘*’s:
7 . . . . . . . 7 . . . . . . 6 . . . . . . C 6 . . . . . /-C 5 . . . . . . * 5 . . . . . | * 4 * * * * * . * 4 * * * * * | * 3 . . . . * . . 3 . . . . * | . 2 . . . . * . . 2 . . . . * | . 1 . C . . * . . 1 . C . . * | . 0 . . . . . . . 0 . \-------/ . 0 1 2 3 4 5 6 0 1 2 3 4 5 6
Determine the minimum number of mirrors M that must be installed to maintain laser communication between the two cows, a feat which is always possible in the given test data.
The cows have switched to using lasers to communicate.
On W*H’s pasture, there are trees and stones blocking the laser in some places, so the cows plan to use a diagonal mirror for laser communication. The positions of the two cows are fixed, and the diagonal mirror can rotate the light 90 degrees.
Input format
* Line 1: Two space separated integers: W and H
* Lines 2..H + 1: The entire pasture.
Output format
* Line 1: A single integer: M
Translation of title
Sample input and output
Enter #1 to copy
7 8 ?… ......C ?…* *****.* ....*.. ....*.. .C..*.. ?…
Output #1 Copy
3
This question is very similar to the previous question, but you can’t do it with the same idea, it will time out
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 105;
string str[N];
int f[N][N],n,m,y11,x11,y22,x22,h,v[N][N];
typedef struct st {
int y, x, w, d;
}st;
int ay[] = {0,1,0,-1 }, ax[] = { 1,0,-1,0 };
int fc(int a, int b) {
int k1 = a + 1;
int k2 = a - 1;
if (k1 == b || k2 == b) {
return 0;
}
return 1;
}
void bfs() {
queue<st>q;
f[y11][x11] = 0;
v[y11][x11] = 1;
for (int i = 0; i < 4; i ++ ) {
for (int j = 1; j <= h; j ++ ) {
int ty = y11 + ay[i] * j;
int tx = x11 + ax[i] * j;
\t\t\t
if (ty<1 || ty>n || tx > m || tx < 1||str[ty][tx]=='*')
break;
f[ty][tx] = 0;
v[ty][tx] = 1;
q.push({ ty,tx,0,i });
}
}
st s;
while (!q.empty()) {
s = q. front();
q. pop();
for (int i = 0; i < 4; i ++ ) {
int w;
w = s.w + 1;
for (int j = 1; j <= h; j ++ ) {
int ty = s.y + ay[i] * j;
int tx = s.x + ax[i] * j;
if (ty > n || ty < 1 || tx<1 || tx>m || str[ty][tx] == '*' )
break;
if ( v[ty][tx]) {
continue;
}
f[ty][tx] = w;
v[ty][tx] = 1;
q.push({ ty,tx,w,i });
if (ty == y22 & amp; & amp; tx == x22) {
return;
}
}
}
}
}
int main() {
scanf("%d%d", &m, &n);
h = max(n, m);
for (int i = 1; i <= n; i ++ ) {
cin >> str[i];
str[i].insert(0, " ");
for (int j = 1; j <= m; j ++ ) {
if (str[i][j] == 'C' & &y11==0) {
y11 = i;
x11 = j;
}
else if (str[i][j] == 'C') {
y22 = i;
x22 = j;
}
}
memset(f[i], 0x3f3f3f3f, sizeof(f[i]));
}
bfs();
cout << f[y22][x22] << endl;
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treeHome pageOverview 48848 people are studying systematically