One piece, its 1, 6 face 2, 4, 3, 5 surface relative, now give a M * N chessboard, pieces at first in (1, 1) point,

Put a given state, now requires with the least amount of steps from (1, 1) to (M, N), and 1 for


Algorithm analysis algorithm is breadth-first search algorithm is easier to think of, as a result of the search tree branches of the tree is 3 fork, very easy to "timeout",
Even with the terms of pruning effect is still not clear,

We analyze the problem: for a piece, its only a total of 24 kinds of state, at point (1, 1), the right back to the point (2, 1),
Roll up to (1, 2), and the state of the arbitrary point (I, J) is the (I - 1, J) and (I, J - 1) state derived,
So, if regulation pawn can up and rolling to the right, you can use the method of dynamic programming will arrive at point (M, N) of all possible
State is derived, and if can only be reached up and back to right (M, N), this method must be the best,
So, we start from (1, 1) to carry on the breadth first search, for each node will be extended out a dynamic programming,
Until the dynamic programming to find the solution, or breadth-first search to find a solution, which can guarantee the optimal solution,


Use simple search to timeout, when M, N is bigger can use dynamic programming

For a piece, a total of 24 kinds of state, at point (1, 1), the right back to the point (2, 1), roll up to the point of (1, 2).

And the state of the arbitrary point (I, J) is the (I - 1, J) and (I, J - 1) damage state is derived, so if the pawn can upward and to the right

Roll, you can use the method of dynamic programming will arrive at point (M, N) of all possible states. Obviously, from (1, 1) to (M, N) these

State of the optimal path, if there is 1 on oriented in these states, have to find the solution. If not, then you can start point (M, N) breadth

Search to (M, N) point state set as the initial state, each extension step, check whether there is the current state of the set of state and to state grid group

In the state of the same, if any, by the dynamic programming of optimality optimality and breadth search can guarantee to find the optimal solution.

CodePudding user response:

First of all, it's not called pieces called dice,

1 face, rolling four steps in the direction of X or Y back into 1 face on,
So the first X, Y direction whole four steps away: S1=(((M - 1), 4) + ((N - 1), 4)) * 4
The rest of the distance
M2=(M - 1) Mod 4
N2=(N - 1) Mod 4
Equivalent to o (1, 1) to (M2 + 1, n + 1) solutions, is at most 5 x5 grid, dice 6, 5 * 5 * 6=120 state,
Both in breadth and depth are easy to reach the 120 state of the least steps out,
Only for a time, any (M, N) (M2, N2), in accordance with the above obtained in S2=1) (M2, N2, face at least count
Final step is S1 + S2

CodePudding user response:

Correction: S2=(M2 , steps 1) least

CodePudding user response:

refer to the original poster laoau127 response:

one piece, the surface of 1, 6 2, 3, 5 surface relative, now give a M * N chessboard, pieces at first in (1, 1) point,

Put a given state, now requires with the least amount of steps from (1, 1) to (M, N), and 1 for
.

For any of the M and N, it won't appear the situation of "no solution"?

CodePudding user response:

There are solutions,
Such as in (1, 1) to dig out the remaining six on a surface:
A: right, down, left, on the left side of the original to the above, A total of four initial direction, so can turn to the above four sides,
B: right, bottom, bottom, left, and, on the original bottom turned over to the above,

CodePudding user response:

reference 4 floor Tiger_Zhao response:

has a solution,
Such as in (1, 1) to dig out the remaining six on a surface:
A: right, down, left, on the left side of the original to the above, A total of four initial direction, so can turn to the above four sides,
B: right, bottom, bottom, left, and, on the original bottom turned over to the above,

CodePudding user response:

How to write code, who will write

CodePudding user response:

Algorithm, write the code to your own thinking,
After all, not a few minutes to finish writing the code, who are so free ah,