Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "bufio"
- "fmt"
- "os"
- "strconv"
- "strings"
- )
- type point struct {
- x int
- y int
- steps int
- figureType rune
- }
- var directionsK = [][]int{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}}
- var directionsG = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
- func isValidMove(x, y, n int) bool {
- return x >= 0 && x < n && y >= 0 && y < n
- }
- func minMoves(chessboard [][]rune, n, startX, startY, targetX, targetY int) int {
- queue := []point{{startX, startY, 0, 'K'}}
- visitedK := make(map[int]bool)
- visitedK[startX*n+startY] = true
- visitedG := make(map[int]bool)
- for len(queue) > 0 {
- curr := queue[0]
- queue = queue[1:]
- if curr.x == targetX && curr.y == targetY {
- return curr.steps
- }
- switch curr.figureType {
- case 'G':
- for _, dir := range directionsG {
- newX, newY := curr.x+dir[0], curr.y+dir[1]
- if isValidMove(newX, newY, n) && !visitedG[newX*n+newY] {
- newFigureType := 'G'
- if chessboard[newX][newY] == 'K' {
- newFigureType = 'K'
- visitedK[newX*n+newY] = true
- }
- queue = append(queue, point{newX, newY, curr.steps + 1, newFigureType})
- visitedG[newX*n+newY] = true
- }
- }
- case 'K':
- for _, dir := range directionsK {
- newX, newY := curr.x+dir[0], curr.y+dir[1]
- if isValidMove(newX, newY, n) && !visitedK[newX*n+newY] {
- newFigureType := 'K'
- if chessboard[newX][newY] == 'G' {
- newFigureType = 'G'
- visitedG[newX*n+newY] = true
- }
- queue = append(queue, point{newX, newY, curr.steps + 1, newFigureType})
- visitedK[newX*n+newY] = true
- }
- }
- }
- }
- return -1
- }
- func main() {
- scanner := bufio.NewScanner(os.Stdin)
- buf := make([]byte, 1e3)
- scanner.Buffer(buf, 1e3)
- scanner.Scan()
- n, _ := strconv.Atoi(strings.Split(scanner.Text(), " ")[0])
- chessboard := make([][]rune, n)
- for i := range chessboard {
- scanner.Scan()
- fields := strings.Fields(scanner.Text())
- chessboard[i] = make([]rune, n)
- for j := 0; j < len(fields[0]); j++ {
- chessboard[i][j] = []rune(fields[0])[j]
- }
- }
- var startX, startY, targetX, targetY int
- for i := 0; i < n; i++ {
- for j := 0; j < n; j++ {
- if chessboard[i][j] == 'S' {
- startX, startY = i, j
- } else if chessboard[i][j] == 'F' {
- targetX, targetY = i, j
- }
- }
- }
- fmt.Println(minMoves(chessboard, n, startX, startY, targetX, targetY))
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement