#!/bin/python3

def isValid(pos, grid):    
    #if [0, 0] <= nextMove < dims:
    
    if pos[0] >= 0 and pos[0] < len(grid) and pos[1] >= 0 and pos[1] < len(grid[0]):
        if grid[pos[0]][pos[1]] == '.':
            return True
    return False

def toKey(pos):
    return "%d.%d" % (pos[0], pos[1])

def minimumMoves(grid, startX, startY, goalX, goalY):
    moves = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    start = [startX, startY]
    goal = [goalX, goalY]
    
    visited = {toKey(start): 0}
    q = [start[:]] # insert a copy of start[]
    while len(q) > 0:
        cur, q = q[0], q[1:]
        dist = visited[toKey(cur)]
        
        for move in moves:
            nextMove = cur[:]
            while True:
                nextMove[0] = nextMove[0] + move[0]
                nextMove[1] = nextMove[1] + move[1]
                if not isValid(nextMove, grid): 
                    break
                if nextMove == goal:
                    return dist + 1
                if toKey(nextMove) not in visited:
                    visited[toKey(nextMove)] = dist + 1
                    q.append(nextMove[:]) # insert a copy of nextMove[]
    return -1

def test(ans, exp):
    if ans == exp:
        print("[PASS] ans = %d" % (ans))
    else:
        print("[FAIL] ans = %d, exp = %d" % (ans, exp))

if __name__ == '__main__':
    grid = []
    grid.append(".x.")
    grid.append(".x.")
    grid.append("...")
    n = minimumMoves(grid, 0, 0, 0, 2)
    test(n, 3)
// C++
using Pos=pair<int,int>;

string pos_to_string(Pos &p) {
    return to_string(p.first)+","+to_string(p.second);
}

void get_neighbors(Pos &cur, vector<string> &grid, vector<Pos> &list) {    
    static vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int size = grid.size();
    for (auto dir : dirs) {
        for (int s = 1; s < size; ++s) {
            int nx = cur.first + dir[0] * s;
            int ny = cur.second + dir[1] * s;            
            if (nx >= 0 && nx < size && ny >= 0 && ny < size && grid[nx][ny] == '.') {
                list.push_back(make_pair(nx, ny));
            } else {
                break;
            }
        }
    }
}

int minimumMoves(vector<string> grid, int startX, int startY, int goalX, int goalY) {
    unordered_map<string, int> visited;
    queue<Pos> q;
    Pos start = make_pair(startX, startY);
    Pos goal = make_pair(goalX, goalY);
    
    if (start == goal) return 0;
    q.push(start);    
    visited[pos_to_string(start)] = 0;
    
    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int dist = visited[pos_to_string(curr)];

        vector<Pos> list;
        get_neighbors(curr, grid, list);
        for (auto next : list) {
            string key = pos_to_string(next);
            if (visited.find(key) == visited.end()) {                
                if (next == goal) return dist + 1;                
                q.push(next);
                visited[key] = dist + 1;
            }
        }
    }
    return -1;
}
