The frog crossing the river | Java clock in brush

This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

I. Title Description:

Ii. Analysis of Ideas:

It is HARD to learn how to do this. The river is divided into many cells, and each cell may contain stones. Only by stepping on stones can you cross the river. Given a list of stones, the frog starts on the first stone. You can only jump one step at the first time. How many steps you can jump after that depends on how far you’ve jumped before. If you jumped K steps last time, you can only jump K minus 1,K,K+1. Ask the frog if he can finally cross the river, that is, reach the last stone. The frog can only go forward.

• So if you look at the problem, every time you go to a position you have 3 choices,k minus 1,k plus 1. My first thought was BFS, because I had read some similar topic analysis by Labuladong before, and I had such an impression.
• The implementation is to use a queue to hold the current possible jump position, and then pull the position from the queue to start the jump. If the retrieved location happens to be our destination, we simply return true. Otherwise start the next jump.
• And how many steps to jump next time, we need to know how we got there, so we need to record a K, which corresponds to how many steps we jumped to the current position, using an extra array.
• Direct submission, no surprises, time out.
• Think about what you can optimize.
• Optimization:

You can record the path of frog jumping, such as K steps to a rock, and then another choice to jump on this rock, can be directly ignored, as a wave of pruning.

Iii. AC Code:

// No pruning, timeout
class Solution {

    / * * *@param Integer[] $stones
     * @return Boolean
     */
    function canCross($stones) {
        $len_n = count($stones);
        $dest = $stones[$len_n - 1];
        $map = [];
        for ($i = 0; $i < $len_n; $i{+ +)$map[$stones[$i]] = 1;
        }
        $queue = new SplQueue(a);$arrK = [];
        $queue->enqueue($stones[0]);
        array_push($arrK.1);
        $first = true;
        while (!$queue->isEmpty()) {
            $size = count($queue);

            for ($i = 0; $i < $size; $i{+ +)$curK = array_shift($arrK);
                if ($first) {
                    $nextSteps = [$curK];
                    $first = false;
                } else {
                    $nextSteps = [$curK.$curK - 1.$curK + 1];
                }
                $curStone = $queue->dequeue();
                if ($curStone= =$dest) {
                    return true;
                }
                foreach ($nextSteps as $nextStep) {
                    if ($nextStep= =0) {
                        continue;
                    }
                    if (isset($map[$nextStep + $curStone]) {$queue->enqueue($nextStep + $curStone);
                        array_push($arrK.$nextStep); }}}}return false; }}/ / by
class Solution {

    / * * *@param Integer[] $stones
     * @return Boolean
     */
    function canCross($stones) {
        $len_n = count($stones);
        $dest = $stones[$len_n - 1];
        $map = [];
        $pathMap = [];
        for ($i = 0; $i < $len_n; $i{+ +)$map[$stones[$i]] = 1;
        }
        $queue = new SplQueue(a);$arrK = [];
        $queue->enqueue($stones[0]);
        array_push($arrK.1);
        $first = true;
        while (!$queue->isEmpty()) {
            $size = count($queue);

            for ($i = 0; $i < $size; $i{+ +)$curK = array_shift($arrK);
                if ($first) {
                    $nextSteps = [$curK];
                    $first = false;
                } else {
                    $nextSteps = [$curK.$curK - 1.$curK + 1];
                }
                $curStone = $queue->dequeue();
                if ($curStone= =$dest) {
                    return true;
                }
                foreach ($nextSteps as $nextStep) {
                    if ($nextStep= =0 || isset($pathMap["{$curStone}_{$nextStep}"]) {continue;
                    }
                    if (isset($map[$nextStep + $curStone]) {$pathMap["{$curStone}_{$nextStep}"] = 1;
                        $queue->enqueue($nextStep + $curStone);
                        array_push($arrK.$nextStep); }}}}return false; }}Copy the code

Iv. Summary:

When you see this kind of choice problem, consider using BFS violence, or try pruning if you run out of time. If you can’t, you have to consider other methods, such as dynamic programming.