D - Snaky Walk
Source: atcoder
Difficulty: 400

Problem Statement
You are given a grid with
H
rows and
W
columns.
Let
(i,j)
denote the cell at the
i
-th row from the top and the
j
-th column from the left.
Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by
H
strings
S_1,S_2,\dots,S_H
, each of length
W
. Specifically, the cell
(i,j)
is a start cell if the
j
-th character of
S_i
is
S
, a goal cell if it is
G
, an empty cell if it is
.
, and an obstacle cell if it is
#
. It is guaranteed that there is exactly one start cell and exactly one goal cell.
You are currently on the start cell.
Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in.
However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)
Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.
More formally, check if there exists a sequence of cells
(i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)
satisfying all of the following conditions. If such a sequence exists, find the minimum value of
k-1
.
For every
1 \leq l \leq k
, it holds that
1 \leq i_l \leq H
and
1 \leq j_l \leq W
, and
(i_l,j_l)
is not an obstacle cell.
(i_1,j_1)
is the start cell.
(i_k,j_k)
is the goal cell.
For every
1 \leq l \leq k-1
,
|i_l - i_{l+1}| + |j_l - j_{l+1}| = 1
.
For every
1 \leq l \leq k-2
, if
i_l \neq i_{l+1}
, then
i_{l+1} = i_{l+2}
.
For every
1 \leq l \leq k-2
, if
j_l \neq j_{l+1}
, then
j_{l+1} = j_{l+2}
.
Constraints
1 \leq H,W \leq 1000
H
and
W
are integers.
Each
S_i
is a string of length
W
consisting of
S
,
G
,
.
,
#
.
There is exactly one start cell and exactly one goal cell.
Input
The input is given from Standard Input in the following format:
H
W
S_1
S_2
\vdots
S_H
Output
If it is possible to reach the goal cell, print the minimum number of moves. Otherwise, print
-1
.
Sample Input 1
3 5
.S#.G
.....
.#...
Sample Output 1
7
As shown in the left figure, you can move as
(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(2,4)\rightarrow(2,5)\rightarrow(1,5)
, reaching the goal cell in
7
moves.
It is impossible in
6
moves or fewer, so the answer is
7
.
Note that you cannot take a path that moves horizontally (or vertically) consecutively without alternating as shown in the right figure.
Sample Input 2
3 5
..#.G
.....
S#...
Sample Output 2
-1
It is not possible to reach the goal cell.
Sample Input 3
8 63
...............................................................
..S...#............................#####..#####..#####..####G..
..#...#................................#..#...#......#..#......
..#####..####...####..####..#..#...#####..#...#..#####..#####..
..#...#..#..#...#..#..#..#..#..#...#......#...#..#..........#..
..#...#..#####..####..####..####...#####..#####..#####..#####..
................#.....#........#...............................
................#.....#........#...............................
Sample Output 3
148

C++ solution:
#include<iostream>
#include<queue>
using namespace std;
int n, m;
int sx, sy, fx, fy;
char g[1005][1005];
bool vis[1005][1005][2];
int dir[4][2] = {1,0,-1,0,0,1,0,-1};

struct Data {
    int x, y, c, h;
};

int bfs() {
    queue<Data> q;
    q.push({sx, sy, 0, 0});
    q.push({sx, sy, 0, 1});
    vis[sx][sy][1] = vis[sx][sy][0] = 1;
    while(!q.empty()) {
        Data cur = q.front();
        q.pop();
        if(cur.x == fx && cur.y == fy) return cur.c;
        for(int i = 0; i < 4; i++) {
            if(i / 2 == cur.h) continue;
            int dx = cur.x + dir[i][0];
            int dy = cur.y + dir[i][1];
            if(dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
            if(g[dx][dy] != '.') continue;
            if(vis[dx][dy][i / 2]) continue;
            vis[dx][dy][i / 2] = 1;
            q.push({dx, dy, cur.c + 1, i / 2});
        }
    }

    return -1;
}


int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> g[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(g[i][j] == 'S') g[i][j] = '.', sx = i, sy = j;
            if(g[i][j] == 'G') g[i][j] = '.', fx = i, fy = j;
        }
    }
    cout << bfs() << endl;
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	buf = make([]byte, 1<<20)
	sc  = bufio.NewScanner(os.Stdin)
	wt  = bufio.NewWriter(os.Stdout)
)

const (
	inf = 1 << 60
	MOD = 998244353
)

func main() {
	/*** INIT ***/
	defer wt.Flush()
	sc.Buffer([]byte{}, inf)
	sc.Split(bufio.ScanWords)

	h, w := InputInt(), InputInt()
	s := make([]string, h)
	sth, stw, glh, glw := -1, -1, -1, -1
	for i := 0; i < h; i++ {
		s[i] = InputString()
		for j := 0; j < w; j++ {
			if s[i][j] == 'S' {
				sth, stw = i, j
			}
			if s[i][j] == 'G' {
				glh, glw = i, j
			}
		}
	}
	ans := inf

	field_ud, field_lr := Slice2dGen(h, w), Slice2dGen(h, w)
	field_ud[sth][stw] = 0
	field_lr[sth][stw] = 0

	nowh, noww := sth, stw
	que := make([]pair, 0, h*w)
	que = append(que, pair{first: nowh, second: noww})
	dh, dw := []int{-1, -1, 1, 1}, []int{1, -1, 1, -1}
	for 0 < len(que) {
		nowh, noww = que[0].first, que[0].second
		que = que[1:]
		for i := 0; i < 4; i++ {
			if check(h, w, nowh+dh[i], noww+dw[i]) && s[nowh+dh[i]][noww] != '#' && s[nowh+dh[i]][noww+dw[i]] != '#' && field_lr[nowh+dh[i]][noww+dw[i]] == inf {
				field_lr[nowh+dh[i]][noww+dw[i]] = field_lr[nowh][noww] + 2
				que = append(que, pair{first: nowh + dh[i], second: noww + dw[i]})
			}
		}
	}
	nowh, noww = sth, stw
	que = append(que, pair{first: nowh, second: noww})
	for 0 < len(que) {
		nowh, noww = que[0].first, que[0].second
		que = que[1:]
		for i := 0; i < 4; i++ {
			if check(h, w, nowh+dh[i], noww+dw[i]) && s[nowh][noww+dw[i]] != '#' && s[nowh+dh[i]][noww+dw[i]] != '#' && field_ud[nowh+dh[i]][noww+dw[i]] == inf {
				field_ud[nowh+dh[i]][noww+dw[i]] = field_ud[nowh][noww] + 2
				que = append(que, pair{first: nowh + dh[i], second: noww + dw[i]})
			}
		}
	}

	ans = Min(field_lr[glh][glw], field_ud[glh][glw])
	dh, dw = []int{0, 0, 1, -1}, []int{1, -1, 0, 0}
	for i := 0; i < 2; i++ {
		if check(h, w, glh+dh[i], glw+dw[i]) {
			ans = Min(ans, field_ud[glh+dh[i]][glw+dw[i]]+1)
		}
	}
	for i := 2; i < 4; i++ {
		if check(h, w, glh+dh[i], glw+dw[i]) {
			ans = Min(ans, field_lr[glh+dh[i]][glw+dw[i]]+1)
		}
	}
	if ans == inf {
		ans = -1
	}
	OutInt(ans)
}

func Min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func check(h, w, nh, nw int) bool {
	if 0 <= nh && nh < h && 0 <= nw && nw < w {
		return true
	}
	return false
}

type pair struct {
	first  int
	second int
}

func Slice2dGen(h, w int) [][]int {
	v := make([][]int, h)
	for i := range v {
		v[i] = make([]int, w)
	}
	default_val := inf
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			v[i][j] = default_val
		}
	}
	return v
}

/*** I/O ***/
func InputInt() int {
	sc.Scan()
	val, _ := strconv.Atoi(sc.Text())
	return val
}

func InputString() string {
	sc.Scan()
	return sc.Text()
}

func OutInt(val int) {
	fmt.Fprintln(wt, val)
}

func OutString(s string) {
	fmt.Fprintln(wt, s)
}

Java solution:
import java.util.*;

public class Main {

    public static void main(String[] args) {
        int h = getInt();
        int w = getInt();
        String[] s = createTiles(w, h, "#");
        boolean checked[][][] = new boolean[h+2][w+2][4];

        record Node(int x, int y, int d, int cost) implements Comparable<Node>{

            @Override
            public int compareTo(Node o) {
                return cost-o.cost;
            }
        }

        ArrayDeque<Node> queue = new ArrayDeque<>();
        for(int i = 1;i <= h; i++){
            for(int j = 1;j <= w;j++){
                if(s[i].charAt(j) == 'S') {
                    for (int k = 0;k < 4;k++) {
                        checked[i][j][k] = true;
                        int nx = j+dx[k];
                        int ny = i+dy[k];
                        if(s[ny].charAt(nx) != '#'){
                            queue.offer(new Node(nx, ny, k,1));
                        }
                    }
                }
            }
        }

        while (!queue.isEmpty()){
            Node node = queue.poll();
            if(s[node.y].charAt(node.x) == 'G'){
                out(node.cost);
                return;
            }


            if(!checked[node.y][node.x][node.d]){
                checked[node.y][node.x][node.d] = true;
                int index = node.d % 2 == 0 ? 1 : 0;
                while(index < 4){
                    int nx = node.x+dx[index];
                    int ny = node.y+dy[index];
                    if(!checked[ny][nx][index] && s[ny].charAt(nx) != '#'){
                        queue.offer(new Node(nx, ny, index,node.cost+1));
                    }
                    index+=2;
                }
            }
        }
        out(-1);
    }


    static int[] dx = new int[]{1, 0, -1, 0};
    static int[] dy = new int[]{0, 1, 0, -1};
    static Comparator<Long> lower = (x, y) -> x.compareTo(y) >= 0 ? 1 : -1; // 指定した値以上の初めての要素の位置
    static Comparator<Long> upper = (x, y) -> x.compareTo(y) > 0 ? 1 : -1;// 指定した値より大きい初めての要素の位置

    static Map<Integer, Set<Integer>> createEdgeMap(int m) {
        return createEdgeMap(m, false);
    }

    static Map<Integer, Set<Integer>> createEdgeMap(int m, boolean d){
        Map<Integer, Set<Integer>> edges = new HashMap<>();

        for(int i = 0;i < m;i++){
            int u = getInt();
            int v = getInt();
            edges.computeIfAbsent(u, key->new HashSet<>()).add(v);
            if(!d) edges.computeIfAbsent(v, key->new HashSet<>()).add(u);
        }

        return edges;
    }

    static long ceil(long n, long d){
        return (n + d - 1) / d;
    }

    static int sqrtI(long n){
        return toInt(Math.sqrt(n));
    }

    static long toLong(double v) {
        return Double.valueOf(v).longValue();
    }

    static int toInt(double v) {
        return Double.valueOf(v).intValue();
    }

    static String[] createTiles(int w, int h, String out){
        String[] s = new String[h + 2];
        s[0] = s[h + 1] = out.repeat(w + 2);

        for (int i = 1; i <= h; i++) {
            s[i] = out + getString() + out;
        }
        return s;
    }

    static void outH(List<?> o){
        int nl = o.size()-1;
        for (int i = 0; i < o.size(); i++) {
            System.out.print(o.get(i)+(i != nl ? " ":"\n"));
        }
    }
    static void out(List<?> o){
        for (Object oo: o) {
            System.out.println(oo);
        }
    }

    static void outH(Object[] o){
        int nl = o.length-1;
        for (int i = 0; i < o.length; i++) {
            System.out.print(o[i]+(i != nl ? " ":""));
        }
        out();
    }

    static void outH(char[] d){
        int nl = d.length-1;
        for (int i = 0; i < d.length; i++) {
            System.out.print(d[i]+(i != nl ? " ":""));
        }
        out();
    }

    static void outH(double[] d){
        int nl = d.length-1;
        for (int i = 0; i < d.length; i++) {
            System.out.print(d[i]+(i != nl ? " ":""));
        }
        out();
    }

    static void outH(int[] in){
        int nl = in.length-1;
        for (int i = 0; i < in.length; i++) {
            System.out.print(in[i]+(i != nl ? " ":""));
        }
        out();
    }

    static void outH(long[] l){
        int nl = l.length-1;
        for (int i = 0; i < l.length; i++) {
            System.out.print(l[i]+(i != nl ? " ":""));
        }
        out();
    }
    static void outH(String[] s){
        int nl = s.length-1;
        for (int i = 0; i < s.length; i++) {
            System.out.print(s[i]+(i != nl ? " ":""));
        }
        out();
    }

    static void out(){
        System.out.println();
    }

    static void out(Object[] o){
        for (Object oo : o) {
            System.out.println(oo);
        }
    }

    static String sortString(String s) {
        char[] a = s.toCharArray();
        Arrays.sort(a);
        return new String(a);
    }

    static String sortStringDesc(String s) {
        return new StringBuilder(sortString(s)).reverse().toString();
    }

    static void out(char[] c){
        for (Character aChar : c) {
            System.out.println(aChar);
        }
    }

    static void out(double[] d){
        for (Double aDouble : d) {
            System.out.println(aDouble);
        }
    }

    static void out(int[] i){
        for (Integer iInteger: i) {
            System.out.println(iInteger);
        }
    }

    static void out(long[] l){
        for (Long lLong: l) {
            System.out.println(lLong);
        }
    }
    static void out(String[] s){
        for (String sString: s) {
            System.out.println(sString);
        }
    }

    static void out(Double d){
        System.out.println(d);
    }


    static void out(Integer i){
        System.out.println(i);
    }

    static void out(Long l){
        System.out.println(l);
    }
    static void out(String s){
        System.out.println(s);
    }

    static void YesOrNo(boolean b){
        System.out.println(b ? "Yes" : "No");
    }
    static void YesOrNo(boolean b, String yes, String no){
        System.out.println(b ? yes : no);
    }
    static void Yes(){
        System.out.println("Yes");
    }

    static void No(){
        System.out.println("No");
    }

    /*
    static StringTokenizer st;
    static InputStreamReader isr = new InputStreamReader(System.in);
    static BufferedReader br = new BufferedReader(isr);
    static String getString()  {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine().trim());
            } catch (IOException e) {
                System.exit(0);
            }
        }
        return st.nextToken();
    }
    static long getLong() {
        return Long.parseLong(getString());
    }
    static int getInt()  {
        return Integer.parseInt(getString());
    }

    static Double getDouble() {
        return parseDouble(getString());
    }

     */
    private static final java.io.InputStream in = System.in;
    private static final byte[] buffer = new byte[1024];
    private static int ptr = 0;
    private static int buflen = 0;

    private static final long LONG_MAX_TENTHS = 922337203685477580L;
    private static final int LONG_MAX_LAST_DIGIT = 7;
    private static final int LONG_MIN_LAST_DIGIT = 8;

    static boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (java.io.IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    static int readByte() {
        if (hasNextByte()) return buffer[ptr++]; else return -1;
    }
    static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }
    static boolean hasNext() {
        while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
        return hasNextByte();
    }
    static String getString() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    static long getLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                int digit = b - '0';
                if (n >= LONG_MAX_TENTHS) {
                    if (n == LONG_MAX_TENTHS) {
                        if (minus) {
                            if (digit <= LONG_MIN_LAST_DIGIT) {
                                n = -n * 10 - digit;
                                b = readByte();
                                if (!isPrintableChar(b)) {
                                    return n;
                                } else if (b < '0' || '9' < b) {
                                    throw new NumberFormatException(
                                            String.format("%d%s... is not number", n, Character.toString(b))
                                    );
                                }
                            }
                        } else {
                            if (digit <= LONG_MAX_LAST_DIGIT) {
                                n = n * 10 + digit;
                                b = readByte();
                                if (!isPrintableChar(b)) {
                                    return n;
                                } else if (b < '0' || '9' < b) {
                                    throw new NumberFormatException(
                                            String.format("%d%s... is not number", n, Character.toString(b))
                                    );
                                }
                            }
                        }
                    }
                    throw new ArithmeticException(
                            String.format("%s%d%d... overflows long.", minus ? "-" : "", n, digit)
                    );
                }
                n = n * 10 + digit;
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    static public int getInt() {
        long nl = getLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    static public double getDouble() {
        return Double.parseDouble(getString());
    }

    static public Long[] getLongArray(int length){
        Long[] array = new Long[length];
        for(int i=0; i<length; i++) array[i] = getLong();
        return array;
    }
    static public Long[] getLongArray(int length, java.util.function.LongUnaryOperator map){
        Long[] array = new Long[length];
        for(int i=0; i<length; i++) array[i] = map.applyAsLong(getLong());
        return array;
    }
    static public int[] getIntArray(int length){
        int[] array = new int[length];
        for(int i=0; i<length; i++) array[i] = getInt();
        return array;
    }
    static public int[] getIntArray(int length, java.util.function.IntUnaryOperator map){
        int[] array = new int[length];
        for(int i=0; i<length; i++) array[i] = map.applyAsInt(getInt());
        return array;
    }
    static public double[] getDoubleArray(int length){
        double[] array = new double[length];
        for(int i=0; i<length; i++) array[i] = getDouble();
        return array;
    }
    static public double[] getDoubleArray(int length, java.util.function.DoubleUnaryOperator map){
        double[] array = new double[length];
        for(int i=0; i<length; i++) array[i] = map.applyAsDouble(getDouble());
        return array;
    }

    static public long[][] getLongMatrix(int height, int width){
        long[][] mat = new long[height][width];
        for(int h=0; h<height; h++) for(int w=0; w<width; w++){
            mat[h][w] = getLong();
        }
        return mat;
    }
    static int[][] getIntMatrix(int height, int width){
        int[][] mat = new int[height][width];
        for(int h=0; h<height; h++) for(int w=0; w<width; w++){
            mat[h][w] = getInt();
        }
        return mat;
    }
    static public double[][] getDoubleMatrix(int height, int width){
        double[][] mat = new double[height][width];
        for(int h=0; h<height; h++) for(int w=0; w<width; w++){
            mat[h][w] = getDouble();
        }
        return mat;
    }

    static public char[][] nextCharMatrix(int height, int width){
        char[][] mat = new char[height][width];
        for(int h=0; h<height; h++){
            String s = getString();
            for(int w=0; w<width; w++){
                mat[h][w] = s.charAt(w);
            }
        }
        return mat;
    }
    public static long mod1097 = 1000000007L;
    public static long mod9982 = 998244353L;
}

JavaScript solution:
function Main(input){
  min = 1e18
  max = -1e18
  class Queue {
  stackPush = [];
  stackPop = [];

  push(value) {
    this.stackPush.push(value);
  }

  shift() {
    if (this.stackPop.length === 0) {
      while (this.stackPush.length > 0) {
        this.stackPop.push(this.stackPush.pop());
      }
    }
    return this.stackPop.pop();
  }
  get length (){
    if (this.stackPop.length === 0) {
      while (this.stackPush.length > 0) {
        this.stackPop.push(this.stackPush.pop());
      }
    }
    return this.stackPop.length;
  }
}
  let abc = "abcdefghijklmnopqrstuvwxyz".split("")
  let ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("")
  let f = 3
  if(f == 0){
    input = parseInt(input.trim())
  }
  if(f == 1){
    input = input.trim().split("\n").map((a)=>parseInt(a))
  }
  if(f == 2){
    input = input.trim().split("\n").map((a)=>a.split(" ").map((b)=>parseInt(b)))
  }
  if(f == 3){
    input = input.trim().split("\n")
  }
  //ここから上は定型文です。
  let [h,w] = input.shift().split(" ").map((a)=>parseInt(a))
  s = input
  s = s.map((a)=>a.split(""))
  queue = new Queue
  yvisited = []
  xvisited = []
  let start;
  for(let i = 0;i<h;i++){
    yvisited.push(new Array(w).fill(-1))
    xvisited.push(new Array(w).fill(-1))
    for(let j = 0;j<w;j++){
      if(s[i][j] == "S"){
        start = [i,j,"yx",0]
      }
    }
  }
  queue.push(start)
  ydirection = [[-1,0],[1,0]]
  xdirection = [[0,-1],[0,1]]
  
  
  while(queue.length){
    let [y,x,search,depth] = queue.shift()
    if(s[y][x] == "G"){
      console.log(depth)
      return
    }
    if(search == "y"||search == "yx"){
      for(let i = 0;i<2;i++){
        let ny = y + ydirection[i][0]
        let nx = x
        if(0 <= ny && ny < h && s[ny][nx] != "#" && yvisited[ny][nx] == -1){
          queue.push([ny,nx,"x",depth+1])
          yvisited[ny][nx] = 1
        }
      }
    }
    if(search == "x"||search == "yx"){
      for(let i = 0;i<2;i++){
        let ny = y
        let nx = x + xdirection[i][1]
        if(0 <= nx && nx < w && s[ny][nx] != "#" && xvisited[ny][nx] == -1){
          queue.push([ny,nx,"y",depth+1])
          xvisited[ny][nx] = 1
        }
      }
    }
  }
  console.log(-1)
}
Main(require("fs").readFileSync(0, "utf8"));

Python solution:
def __Main__():
    n, m = map(int, input().split())
    a = [input() for _ in range(n)]

    sx, sy = -1, -1
    ex, ey = -1, -1

    for i in range(n):
        for j in range(m):
            if a[i][j] == "S":
                sx, sy = i, j
            if a[i][j] == "G":
                ex, ey = i, j

    INF = 10**18

    def f(x, y):
        return x * m + y

    ans = INF
    dist = [INF] * (n * m)
    que = [0] * (n * m)
    l, r = 0, 1

    que[0] = f(sx, sy)
    dist[que[0]] = 0

    d1 = [(-1, 0), (1, 0)]
    d2 = [(0, 1), (0, -1)]

    step = 0

    while l < r:
        for i in range(l, r):
            u = que[l]
            l += 1
            x, y = divmod(u, m)
            for dx, dy in d1 if step else d2:
                nx, ny = x + dx, y + dy
                np = f(nx, ny)

                if 0 <= nx < n and 0 <= ny < m and a[nx][ny] != "#" and dist[np] == INF:
                    dist[np] = dist[u] + 1
                    que[r] = np
                    r += 1
        step ^= 1

    ans = min(ans, dist[f(ex, ey)])
    dist = [INF] * (n * m)
    que = [0] * (n * m)
    l, r = 0, 1

    que[0] = f(sx, sy)
    dist[que[0]] = 0

    d1 = [(-1, 0), (1, 0)]
    d2 = [(0, 1), (0, -1)]

    step = 0

    while l < r:
        for i in range(l, r):
            u = que[l]
            l += 1
            x, y = divmod(u, m)
            for dx, dy in d2 if step else d1:
                nx, ny = x + dx, y + dy
                np = f(nx, ny)

                if 0 <= nx < n and 0 <= ny < m and a[nx][ny] != "#" and dist[np] == INF:
                    dist[np] = dist[u] + 1
                    que[r] = np
                    r += 1
        step ^= 1

    ans = min(ans, dist[f(ex, ey)])

    print(ans if ans != INF else -1)


if __name__ == "__main__":
    __Main__()

Ruby solution:
H,W = gets.split.map(&:to_i)
G = $<.read.bytes+[0]*W
S = G.index ?S.ord
T = G.index ?G.ord
G[S] = G[T] = ?..ord

V1 = G.map{|b| -1 if b!=?..ord }
V2 = *V1
V1[S] = V2[S] = v = 0
Q1,Q2 = [S],[S]
until Q1.empty? && Q2.empty?
	v += 1
	z1,z2 = Q1.size,Q2.size
	z1.times{ # 横へ
		s = Q1.shift
		V2[s+1] ||= (Q2<<s+1; v)
		V2[s-1] ||= (Q2<<s-1; v)
	}
	z2.times{ # 縦へ
		s = Q2.shift
		V1[s+W+1] ||= (Q1<<s+W+1; v)
		V1[s-W-1] ||= (Q1<<s-W-1; v)
	}
end

p(([V1[T]||-1,V2[T]||-1]-[-1]).min||-1)