Computer scienceProgramming languagesGolangTypes and data structuresStack and Queue

Using stack in Go

Theory

Finding a path

Report a typo

Wow! This problem is kind of tricky. If you're ready to put your thinking cap on, brace yourself, and good luck! Otherwise, you can skip it for now and return any time later.

Here is a real class of tasks that use stacks: pathfinding. You will get a lot of numbers. The first number is the width of the scheme, the second is the height. The remaining values are the layout. The layout consists of integers:

  • 8 is a wall (you can't pass through);

  • 0 is an empty space (you can pass through);

  • 1 is the beginning of a journey;

  • 9 is the end of a journey.

You can only move in four directions (left, right, up, down). All paths in the layout are represented by corridors. And the question is: will you be able to go from start to finish?

Let's analyze the first two examples. At the first example you get a layout 4 by 5 with layout:

8 8 8 8
8 0 9 8
8 8 0 8
8 1 0 8
8 8 8 8

This is a fairly simple layout, at the starting point you can only move in one direction (to the right). After that, you take two steps up, and the journey ends. The answer is true.

The second example has almost the same scheme, but contains one additional wall:

8 8 8 8
8 0 9 8
8 8 0 8
8 1 8 8
8 8 8 8

The wall closes only one possible path! This means that the problem has no solution, and the answer is false.

Sample Input 1: 

4
5
8 8 8 8
8 0 9 8
8 8 0 8
8 1 0 8
8 8 8 8

Sample Output 1: 

true

Sample Input 2: 

4
5
8 8 8 8
8 0 9 8
8 8 0 8
8 1 8 8
8 8 8 8

Sample Output 2: 

false
Write a program in Go
package main

import (
"errors"
"fmt"
)

// first you need to change a stack
// to store the coordinates in []int variable
type XYStack struct {
storage [][]int
}

func (s *XYStack) Push(value ?) {
s.storage = append(s.storage, value)
}

func (s *XYStack) Pop() (?, error) {
last := len(s.storage) - 1
if last <= -1 {
return ?, errors.New("stack is empty")
}

value := s.storage[last]
s.storage = s.storage[:last]

return value, nil
}

func main() {
// don't worry about the input data
// the readLayout() function will do it for you (don't touch it!)
layout, start, finish := readLayout()

fmt.Println(ifPathExists(layout, start, finish))
}
___

Create a free account to access the full topic