Break a Prison
Source: aizu

Break a Prison
Problem Statement

Jennifer is a software engineer at a Tech company. Her company decided to join ICPC (Inter-Company Prison breaking Contest) and she was chosen as a representative of the company.

In ICPC, every participant needs to escape from a prison. The prison can be represented as an $n \times m$ grid i.e. it has $n$ rows and $m$ columns of rooms. The room in the $i$-th row and $j$-th column in the prison is denoted as room $(i, j)$. Two rooms $(i_1, j_1)$ and $(i_2, j_2)$ are adjacent if and only if $|i_2 − i_1| + |j_2 − j_1| = 1$. Weirdly, there is an unlocked door between each pair of adjacent rooms. Some rooms in the prison are under surveillance. Participants can move to a room only if it's not under surveillance. A participant will start from a room. The goal of all participants is to reach an exit. It's guaranteed that the room with the exit and the room that participants start from are not under surveillance.

To show talents in the company, the CEO asked Jeniffer not to turn right during the contest. In other words, there should not be any two consecutive moves between rooms that fulfill the following condition.

Condition: Given that Jeniffer moved from room $(i_1, j_1)$ to $(i_2, j_2)$ , and then she moved to room $(i_3, j_3)$. Then, $(i_2 − i_1) \times (j_3 − j_2) − (j_2 − j_1) \times (i_3 − i_2) = −1$ holds.


Figure B.1. Example of allowed and denied moves


For example, in figure B.1., if the last move is along the dashed arrow, you cannot move downward but you can move the other three directions.

Note that U-turns are allowed with this condition.

As a Jeniffer's colleague, your mission is to write a program to find the minimum number of moves between rooms to reach the exit for her.

Input

The input consists of a single test case in the following format.

$n$ $m$
$c_{1,1}c_{1,2} ... c_{1,m}$
$c_{2,1}c_{2,2} ... c_{2,m}$
$\vdots$
$c_{n,1}c_{n,2} ... c_{n,m}$


$n$ and $m$ represent the size of the prison, each of which is an integer between $2$ and $500$. $c_{i,j}$ ($1 \leq i \leq n, 1 \leq j \leq m$) is a character that describes the status of a room in the $i$-th row and $j$-th column. The character is either

‘S' which means a start room for a participant,
‘E' which means a room with an exit,
‘.' which means the room is not under surveillance, or
‘#' which means the room is under surveillance.

It is guaranteed that ‘S' and ‘E' appear exactly once in the input respectively.

Output

Print the minimum number of moves between rooms for Jenniffer to reach the exit. If she cannot reach the exit, print -1

Sample Input 1
2 4
S..#
..E.

Sample Output 1
3

Sample Input 2
2 4
S..#
##E.

Sample Output 2
-1

Sample Input 3
2 4
S...
##E.

Sample Output 3
5


In Sample Input 3, one of the optimal routes is below.


Figure B.2. The optimal route in Sample Input 3


C++ solution:
// AOJ #3613
// Break a Prison 2025.1.28

#include <bits/stdc++.h>
using namespace std;

// 移動方向を表すベクトル (上, 右, 下, 左)
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};
bool visited[501][501][5]; 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    
    vector<string> grid(n);
    int sr, sc; // start
    int er, ec; // exit
    for(int i = 0; i < n; i++){
        cin >> grid[i];
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 'S') sr = i, sc = j;
            else if(grid[i][j] == 'E') er = i, ec = j;
        }
    }

    // BFS 用キュー: (行, 列, 進行方向, 移動回数)
    queue<tuple<int,int,int,int>> que;

    // スタート地点をキューに入れる (方向は4で初期化, 移動回数0)
    visited[sr][sc][4] = true;
    que.push({sr, sc, 4, 0});

    // BFS 開始
    while(!que.empty()){
        auto [r, c, d, dist] = que.front();
        que.pop();

        // もし出口に到達したら dist を出力して終了
        if(r == er && c == ec){
            cout << dist << endl;
            return 0;
        }

        // 次の方向として 0～3 を試す (上, 右, 下, 左)
        for(int nd = 0; nd < 4; nd++){
            // もし d != 4 なら右折 (nd == (d+1)%4) を禁止
            if(d != 4 && nd == (d + 1) % 4){
                continue; // 右折となるのでスキップ
            }
            int nr = r + dr[nd];
            int nc = c + dc[nd];

            // 範囲内 & 監視対象('#') でない & 未訪問 なら移動可能
            if(nr >= 0 && nr < n && nc >= 0 && nc < m){
                if(grid[nr][nc] != '#' && !visited[nr][nc][nd]){
                    visited[nr][nc][nd] = true;
                    que.push({nr, nc, nd, dist + 1});
                }
            }
        }
    }

    // BFS ですべて探索しても出口に辿り着けない場合は -1 を出力
    cout << -1 << endl;
    return 0;
}

Go solution:
package main

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

type State struct {
	r, c, d, dist int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	m, _ := strconv.Atoi(scanner.Text())

	grid := make([]string, n)
	var sr, sc, er, ec int

	for i := 0; i < n; i++ {
		scanner.Scan()
		grid[i] = scanner.Text()
		for j := 0; j < m; j++ {
			if grid[i][j] == 'S' {
				sr, sc = i, j
			} else if grid[i][j] == 'E' {
				er, ec = i, j
			}
		}
	}

	// Directions: up, right, down, left
	dr := []int{-1, 0, 1, 0}
	dc := []int{0, 1, 0, -1}

	visited := make([][][]bool, n)
	for i := range visited {
		visited[i] = make([][]bool, m)
		for j := range visited[i] {
			visited[i][j] = make([]bool, 5) // 0-3 for directions, 4 for initial
		}
	}

	queue := []State{}
	queue = append(queue, State{sr, sc, 4, 0})
	visited[sr][sc][4] = true

	found := -1

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		if current.r == er && current.c == ec {
			found = current.dist
			break
		}

		for nd := 0; nd < 4; nd++ {
			if current.d != 4 && nd == (current.d+1)%4 {
				continue // skip right turns
			}
			nr := current.r + dr[nd]
			nc := current.c + dc[nd]

			if nr >= 0 && nr < n && nc >= 0 && nc < m {
				if grid[nr][nc] != '#' && !visited[nr][nc][nd] {
					visited[nr][nc][nd] = true
					queue = append(queue, State{nr, nc, nd, current.dist + 1})
				}
			}
		}
	}

	fmt.Println(found)
}

Java solution:
import java.util.*;

public class Main {
    // Directions: up, right, down, left (0, 1, 2, 3)
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine(); // consume the rest of the line

        char[][] grid = new char[n][m];
        int sr = -1, scStart = -1; // start position
        int er = -1, ec = -1;      // exit position

        for (int i = 0; i < n; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < m; j++) {
                grid[i][j] = line.charAt(j);
                if (grid[i][j] == 'S') {
                    sr = i;
                    scStart = j;
                } else if (grid[i][j] == 'E') {
                    er = i;
                    ec = j;
                }
            }
        }

        // Visited array: [row][col][last direction (0-3), 4 means no previous direction]
        boolean[][][] visited = new boolean[n][m][5];
        Queue<State> queue = new LinkedList<>();

        // Initial state: start position, direction 4 (no previous direction), distance 0
        queue.add(new State(sr, scStart, 4, 0));
        visited[sr][scStart][4] = true;

        while (!queue.isEmpty()) {
            State current = queue.poll();
            int r = current.r;
            int c = current.c;
            int d = current.direction;
            int dist = current.distance;

            if (r == er && c == ec) {
                System.out.println(dist);
                return;
            }

            for (int nd = 0; nd < 4; nd++) {
                // Skip if this is a right turn from the previous direction
                if (d != 4 && nd == (d + 1) % 4) {
                    continue;
                }

                int nr = r + dr[nd];
                int nc = c + dc[nd];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    if (grid[nr][nc] != '#' && !visited[nr][nc][nd]) {
                        visited[nr][nc][nd] = true;
                        queue.add(new State(nr, nc, nd, dist + 1));
                    }
                }
            }
        }

        System.out.println(-1);
    }

    static class State {
        int r, c;
        int direction;
        int distance;

        State(int r, int c, int direction, int distance) {
            this.r = r;
            this.c = c;
            this.direction = direction;
            this.distance = distance;
        }
    }
}

JavaScript solution:
const { Queue } = require('datastructures-js');

const dr = [-1, 0, 1, 0]; // Directions: up, right, down, left
const dc = [0, 1, 0, -1];

function solve() {
    const fs = require('fs');
    const input = fs.readFileSync(0, 'utf8').trim().split('\n');
    const firstLine = input[0].split(' ');
    const n = parseInt(firstLine[0], 10);
    const m = parseInt(firstLine[1], 10);
    
    const grid = [];
    let sr, sc, er, ec;
    for (let i = 1; i <= n; i++) {
        const line = input[i].trim();
        grid.push(line);
        for (let j = 0; j < m; j++) {
            if (line[j] === 'S') {
                sr = i - 1;
                sc = j;
            } else if (line[j] === 'E') {
                er = i - 1;
                ec = j;
            }
        }
    }

    // Initialize visited array: [n][m][5] (direction 4 is initial)
    const visited = Array(n).fill().map(() => 
        Array(m).fill().map(() => 
            Array(5).fill(false)
        )
    );

    const queue = new Queue();
    queue.enqueue([sr, sc, 4, 0]);
    visited[sr][sc][4] = true;

    while (!queue.isEmpty()) {
        const [r, c, d, dist] = queue.dequeue();

        if (r === er && c === ec) {
            console.log(dist);
            return;
        }

        for (let nd = 0; nd < 4; nd++) {
            if (d !== 4 && nd === (d + 1) % 4) {
                continue; // Skip right turns
            }
            const nr = r + dr[nd];
            const nc = c + dc[nd];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                if (grid[nr][nc] !== '#' && !visited[nr][nc][nd]) {
                    visited[nr][nc][nd] = true;
                    queue.enqueue([nr, nc, nd, dist + 1]);
                }
            }
        }
    }

    console.log(-1);
}

solve();

Python solution:
import sys
from collections import deque

def solve():
    n, m = map(int, sys.stdin.readline().split())
    grid = []
    sr, sc = -1, -1  # start position
    er, ec = -1, -1  # exit position
    for i in range(n):
        line = sys.stdin.readline().strip()
        grid.append(line)
        for j in range(m):
            if grid[i][j] == 'S':
                sr, sc = i, j
            elif grid[i][j] == 'E':
                er, ec = i, j
    
    # Directions: up, right, down, left (0, 1, 2, 3)
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]
    
    # Visited structure: visited[r][c][d] indicates whether (r,c) was visited with direction d
    visited = [[[False for _ in range(5)] for __ in range(m)] for ___ in range(n)]
    # Initial direction is 4 (no previous direction)
    q = deque()
    q.append((sr, sc, 4, 0))
    visited[sr][sc][4] = True
    
    while q:
        r, c, d, dist = q.popleft()
        if r == er and c == ec:
            print(dist)
            return
        
        for nd in range(4):
            # Check if moving in direction nd is a right turn from d
            if d != 4 and nd == (d + 1) % 4:
                continue  # skip right turns
            nr = r + dr[nd]
            nc = c + dc[nd]
            if 0 <= nr < n and 0 <= nc < m:
                if grid[nr][nc] != '#' and not visited[nr][nc][nd]:
                    visited[nr][nc][nd] = True
                    q.append((nr, nc, nd, dist + 1))
    
    print(-1)

solve()

Ruby solution:
require 'set'

# Directions: up, right, down, left (0, 1, 2, 3)
DIRECTIONS = [[-1, 0], [0, 1], [1, 0], [0, -1]].freeze

# Read input
n, m = gets.split.map(&:to_i)
grid = []
start_pos = nil
exit_pos = nil

n.times do |i|
  line = gets.chomp
  grid << line
  line.chars.each_with_index do |char, j|
    start_pos = [i, j] if char == 'S'
    exit_pos = [i, j] if char == 'E'
  end
end

# Initialize BFS queue: [row, col, last_direction, distance]
queue = []
visited = Array.new(n) { Array.new(m) { Array.new(4, false) } }

# Start from 'S' with no previous direction (represented as -1)
sr, sc = start_pos
queue << [sr, sc, -1, 0]

result = -1

until queue.empty?
  r, c, last_dir, dist = queue.shift

  # Check if we reached the exit
  if r == exit_pos[0] && c == exit_pos[1]
    result = dist
    break
  end

  # Try all 4 possible directions
  DIRECTIONS.each_with_index do |(dr, dc), current_dir|
    # Skip right turns (current_dir == (last_dir + 1) % 4)
    next if last_dir != -1 && current_dir == (last_dir + 1) % 4

    nr = r + dr
    nc = c + dc

    # Check bounds and if cell is accessible and not visited with this direction
    if nr.between?(0, n-1) && nc.between?(0, m-1) && 
       grid[nr][nc] != '#' && !visited[nr][nc][current_dir]
      visited[nr][nc][current_dir] = true
      queue << [nr, nc, current_dir, dist + 1]
    end
  end
end

puts result