6

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))
}