extern crate core;

use std::fmt;
use std::cmp::{Ordering, min, max};
use std::fmt::{Display, Error, Formatter};
use std::f32::MAX;
use std::ops::{Add, Sub, Mul, Div, Neg, Index, IndexMut};

fn show<T: Display>(vec: &Vec<T>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        print!("[{}", vec[0]);
        for i in 1 .. vec.len() {
            print!(", {}", vec[i]);
        }
        println!("]");
    }
}
fn show2<T: Display>(vec: &Vec<Vec<T>>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        for l in vec {
            show(l);
        }
    }
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! read_value{
    () => {
        read_line!().trim().parse().ok().unwrap()
    }
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
macro_rules! let_mut_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let mut $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
#[derive(Copy, Clone, Eq, PartialEq)]
struct Point {
    x: i32, y: i32
}
impl Point {
    fn neighbors(&self) -> Vec<Point> {
        vec![Point{x: self.x + 1, y: self.y}, Point{x: self.x - 1, y: self.y}, Point{x: self.x, y: self.y + 1}, Point{x: self.x, y: self.y - 1}]
    }
}
pub struct Grids {
    lines: Vec<Vec<char>>,
    pub height: i32, pub width: i32,
}
#[derive(Copy, Clone, Eq, PartialEq)]
enum State {
    Empty, Block
}
impl Grids {
    fn new(lines: Vec<Vec<char>>) -> Grids {
        let h = lines.len() as i32;
        let w = lines[0].len() as i32;
        Grids{lines: lines, height: h, width: w}
    }
    fn contains(&self, coordinate: Point) -> bool {
        0 <= coordinate.y && coordinate.y < self.height && 0 <= coordinate.x && coordinate.x < self.width
    }
    fn at(&self, index: Point) -> Option<State> {
        if self.contains(index) {
            Some(match self.lines[index.y as usize][index.x as usize] {
                '#' => State::Block,
                _ => State::Empty
            })
        }else {
            None
        }
    }
}
fn read_grids(h: usize) -> Grids {
    let mut lines = Vec::with_capacity(h);
    for _ in 0 .. h {
        lines.push(read_line!().trim().chars().collect());
    }
    Grids::new(lines)
}

fn main() {
    let_all!(h: usize, w: usize);
    let mut lines = Vec::with_capacity(h);
    for _ in 0 .. h {
        lines.push(read_line!().trim().chars().collect())
    }
    let mut grid = Grids::new(lines.clone());
    let mut start = Point{x: 0, y: 0};
    let mut goal = Point{x: 0, y: 0};
    for y in 0 .. h {
        for x in 0 .. w {
            match lines[y][x] {
                'S' => start = Point{x: x as i32, y: y as i32},
                'G' => goal = Point{x: x as i32, y: y as i32},
                _ => {}
            }
        }
    }
    let start = start;
    let goal = goal;
    let mut memo = vec![vec![vec![-1; w]; h]; 2];
    memo[0][start.y as usize][start.x as usize] = 0;
    let mut min_step = -1;
    let_mut_all!(n: usize);
    let_mut_all!(next_time: usize);
    for t in 1 .. 602 {
        if t == next_time {
            grid = read_grids(h);
            n -= 1;
            if n != 0 {
                next_time = read_value!();
            }
        }
        for y in 0 .. h {
            for x in 0 .. w {
                if let Some(State::Empty) = grid.at(Point{x: x as i32, y: y as i32}) {
                    memo[t % 2][y][x] = memo[(t + 1) % 2][y][x];
                }else {
                    memo[t % 2][y][x] = -1;
                }
            }
        }
        for y in 0 .. h {
            for x in 0 .. w {
                let current = Point{x: x as i32, y: y as i32};
                if memo[(t + 1) % 2][y][x] != -1 {
                    for Point{x: nx, y: ny} in current.neighbors() {
                        if let Some(State::Empty) = grid.at(Point{x: nx, y: ny}) {
                            if memo[t % 2][ny as usize][nx as usize] == -1 || memo[t % 2][ny as usize][nx as usize] > memo[(t + 1) % 2][y][x] {
                                memo[t % 2][ny as usize][nx as usize] = memo[(t + 1) % 2][y][x] + 1;
                            }
                        }
                    }
                }
            }
        }
        if memo[t % 2][goal.y as usize][goal.x as usize] != -1 && (min_step == -1 || min_step > memo[t % 2][goal.y as usize][goal.x as usize]) {
            min_step = memo[t % 2][goal.y as usize][goal.x as usize];
        }
    }
    println!("{}", min_step);
}


Measured memory_bytes: 5068