地牢逃脱

宽度优先搜索

从起点出发，利用BFS求到任意位置的最短距离矩阵，其中表示起点到位置的最短距离。然后遍历这个矩阵，对于任意一个位置，如果它在地牢矩阵中可以通行，它就可以成为地牢的出口，找到这些位置的最大值就可以了。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        char[][] grid = new char[n][];
        for(int i = 0; i < n; i++){
            grid[i] = br.readLine().toCharArray();
        }
        params = br.readLine().split(" ");
        int x0 = Integer.parseInt(params[0]), y0 = Integer.parseInt(params[1]);
        int k = Integer.parseInt(br.readLine());
        int[] dx = new int[k], dy = new int[k];
        for(int i = 0; i < k; i++){
            params = br.readLine().split(" ");
            dx[i] = Integer.parseInt(params[0]);
            dy[i] = Integer.parseInt(params[1]);
        }
        int maxStep = 0;
        int[][] dis = bfs(grid, x0, y0, dx, dy);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == '.'){
                    // 所有能走的地方都可以作为出口
                    maxStep = Math.max(maxStep, dis[i][j]);
                }
            }
        }
        System.out.println(maxStep == Integer.MAX_VALUE? -1: maxStep);
    }
    
    private static int[][] bfs(char[][] grid, int x0, int y0, int[] dx, int[] dy) {
        int n = grid.length, m = grid[0].length;
        int[][] dis = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dis[i][j] = Integer.MAX_VALUE;
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x0, y0});
        dis[x0][y0] = 0;
        while(!queue.isEmpty()){
            int queueSize = queue.size();
            for(int j = 0; j < queueSize; j++){
                int[] cur = queue.poll();
                int x = cur[0], y = cur[1];
                for(int i = 0; i < dx.length; i++){
                    int x_ = cur[0] + dx[i];
                    int y_ = cur[1] + dy[i];
                    if(0 <= x_ && x_ < n && 0 <= y_ && y_ < m && grid[x_][y_] == '.'){
                        if(dis[x_][y_] > dis[x][y] + 1){
                            // 类似迪杰斯特拉算法，距离变小了就更新
                            dis[x_][y_] = dis[x][y] + 1;
                            queue.offer(new int[]{x_, y_});
                        }
                    }
                }
            }
        }
        return dis;
    }
}

import java.util.*;
import java.io.*;
public class Main {
    /**
    *关键描述：地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。
    *这句话的意思是什么呢？结合示离，意思是在可通行的位置上，我们要选择最短路径。但是有多个可通行的位置上，我们要找最远的，若最远不可达输出-1
    *这样问题就转化为最短路径问题，我们要找到最远点的最短路径。使用BFS可以实现。
    */
    public static void main(String[] args) throws Exception{
        String[] arrInput;
        char[] arrChar;
        Deque<Pointer> deque = new ArrayDeque<Pointer>();//使用双端队列做队列
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arrInput = br.readLine().trim().split(" ");
        int n = Integer.parseInt(arrInput[0]);
        int m = Integer.parseInt(arrInput[1]);
        int[][] arrDungeon = new int[n][m];//-1不可通行，0可以通行，整数为到达的步数
        for (int i=0; i<n; i++) {
            arrChar = br.readLine().trim().toCharArray();//应为连续字符没有间隔，用toCharArray转化为字符数组
            for (int j=0; j<m; j++) {
                if (arrChar[j] == '.') {
                    arrDungeon[i][j] = 0;
                } else if (arrChar[j] == 'X') {
                    arrDungeon[i][j] = -1;
                }
            }
        }
        arrInput = br.readLine().trim().split(" ");
        Pointer pointer = new Pointer();
        pointer.x = Integer.parseInt(arrInput[0]);
        pointer.y = Integer.parseInt(arrInput[1]);
        int startxx = pointer.x;
        int startyy = pointer.y;
        deque.offerLast(pointer);//入队
        int intStepCnt = Integer.parseInt(br.readLine().trim());
        int[][] arrStep = new int[intStepCnt][2];
        for (int i=0; i<intStepCnt; i++) {
            arrInput = br.readLine().trim().split(" ");
            arrStep[i][0] = Integer.parseInt(arrInput[0]);
            arrStep[i][1] = Integer.parseInt(arrInput[1]);
        }
        int x = 0;
        int y = 0;
        int x1 = 0;
        int y1 = 0;
        //BFS由近及远
        while (deque.size() > 0) {
            Pointer pointerOne = deque.pollFirst();
            x = pointerOne.x;
            y = pointerOne.y;
            for (int i=0; i<intStepCnt; i++) {
                x1 = x + arrStep[i][0];
                y1 = y + arrStep[i][1];
                if (x1 >= 0 && x1 < arrDungeon.length && y1 >= 0 && y1 < arrDungeon[0].length && arrDungeon[x1][y1] == 0) {//不越界的情况
                    arrDungeon[x1][y1] = arrDungeon[x][y] + 1;
                    Pointer temp = new Pointer();
                    temp.x = x1;
                    temp.y = y1;
                    deque.offerLast(temp);//入队
                }
            }
        }
        int max = 0;
        boolean isHaveCanNotAccessPointer = false;//标记有没有不可达点的
        for (int i=0; i<n; i++) {
            if (isHaveCanNotAccessPointer == true) {
                break;
            }
            for (int j=0; j<m; j++) {
                if ((i != startxx || j != startyy) && arrDungeon[i][j] == 0) {//不是起点若是0就是有不可达点
                    isHaveCanNotAccessPointer = true;
                    break;
                }
                if (arrDungeon[i][j] > max) {
                    max = arrDungeon[i][j];
                }
            }
        }
        if (isHaveCanNotAccessPointer) {
            System.out.println(-1);
        } else {
            System.out.println(max);
        }

    }
    static class  Pointer {//坐标类
        public int x;
        public int y;
    }
}

题解：

题目为广度优先搜索， 和之前不同的是，这个不是搜索最短路径，而是搜索所有点是否可达，首先按照普通的搜索方法搜索，（搜索的步长是题目给定的， 不是之前的四个方向的）遍历所有之后，查看是否所有的点都遍历到了。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main02 {
    public static void main(String[] args){
        int row,col, startx, starty, stepNum, ans;
        String[] gMap;
        int[][] stepMap;
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            ans = -1;
            row = sc.nextInt();
            col = sc.nextInt();
            gMap = new String[row];
            for(int i = 0; i < row; i++){
                gMap[i] = sc.next();
            }
            startx = sc.nextInt();
            starty = sc.nextInt();
            stepNum = sc.nextInt();
            stepMap = new int[stepNum][2];
            for(int i = 0; i < stepNum; i++){
                stepMap[i][0] = sc.nextInt();
                stepMap[i][1] = sc.nextInt();
            }

            Graph graph = new Graph(gMap, stepMap);

            Queue<Point> pointQueue = new LinkedList<Point>();
            Point point = new Point();
            point.x = startx;
            point.y = starty;
            point.steps = 0;
            pointQueue.offer(point);
            graph.graphVis[point.x][point.y][1] = 1;
            while(!pointQueue.isEmpty()){
                Point nowPoint = pointQueue.poll();
                graph.nextStep(nowPoint,pointQueue);
            }
            if( graph.canOut()){
                System.out.println(graph.maxStep);
            }else{
                System.out.println(-1);
            }
        }

    }
}
class Graph{
    public String[] graphMap;
    public int[][] stepMap;
    public int[][][] graphVis;
    public int maxStep;
    Graph(String[] graph, int[][] step){
        maxStep = 0;
        graphMap = graph;
        stepMap = step;
        graphVis = new int[graph.length][graph[0].length()][2];
        for(int i = 0; i < graph.length; i++){
            for(int j = 0; j < graph[0].length(); j++){
                if(graph[i].charAt(j) == '.'){
                    graphVis[i][j][0] = 1;
                }else{
                    graphVis[i][j][0] = 0;
                }

            }
        }

    }
    public boolean isInGraph(int x, int y){
        if(x < graphMap.length && x >= 0 && y < graphMap[0].length() && y >= 0){
            return true;
        }else{
            return false;
        }
    }

    public void nextStep(Point nowPoint, Queue<Point> pointQueue){
        for(int i = 0; i < stepMap.length; i++){
            int nextx = nowPoint.x + stepMap[i][0];
            int nexty = nowPoint.y + stepMap[i][1];
            if(isInGraph(nextx, nexty) && graphMap[nextx].charAt(nexty) == '.' && graphVis[nextx][nexty][1] == 0){
                graphVis[nextx][nexty][1] = 1;
                Point nextPoint = new Point();
                nextPoint.x = nextx;
                nextPoint.y = nexty;
                nextPoint.steps = nowPoint.steps + 1;
                maxStep = Math.max(nextPoint.steps, maxStep);
                pointQueue.offer(nextPoint);
            }
        }
    }

    public boolean canOut(){
        boolean isRight = true;
        for(int i = 0; i < graphVis.length; i++){
            for (int j = 0; j < graphVis[0].length; j++){
                if(graphVis[i][j][0] != graphVis[i][j][1]){
                    isRight = false;
                }
            }
        }
        return isRight;
    }
}
class Point{
    public int x;
    public int y;
    public int steps;
}

package challenge;

import java.util.Scanner;

/**
* @author 作者 Eden:
* @version 创建时间：2018年7月22日 下午6:25:29
* @deprecated:
* 题目描述
    给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出
    发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过
    地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少
    步才可以离开这个地牢。
    输入描述:
    每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。
    接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x0, y0，表示牛
    牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。之后的一行包含
    一个整数 k（0 < k <= 50）表示牛牛合法的步长数，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行
    和列步长（-50 <= dx, dy <= 50）
    输出描述:
    输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛
    可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。
*/

public class PrisonEscape {
    public static char[][] matrix;//迷宫矩阵
    public static int[][] step;//每次可选择移动的行和列步长
    public static int[][] matrixStep;//标记牛牛到每个可行点最大的步数，-1表示障碍，0表示不可达
    public static int maxStep=-1;//最大逃出迷宫的步数，初始值-1代表出不去
    public static int n,m,k;
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int i,j,dx,dy,x0,y0;
        String s;
        char[] c;
        n=input.nextInt();//迷宫矩阵行数
        m=input.nextInt();//迷宫矩阵列数
        matrix = new char[n][m];
        matrixStep = new int[n][m];
        c = new char[m];
        input.nextLine();
        //输入迷宫矩阵
        for(i=0;i<n;i++){
            s=input.nextLine();
            c=s.toCharArray();
            for(j=0;j<m;j++){
                matrix[i][j]=c[j];
                if(c[j]=='X'){
                    matrixStep[i][j]=-1; 
                }else{
                    matrixStep[i][j]=n*m; 
                }
            }
        }
        //牛牛的起始位置
        y0=input.nextInt();
        x0=input.nextInt();
        matrixStep[y0][x0]=-1;
        matrix[y0][x0]='X';
        //牛牛合法的步长数
        k=input.nextInt();
        step = new int[k][2];
        //每次可选择移动的行和列步长
        for(i=0;i<k;i++){
            for(j=1;j>=0;j--){
                step[i][j]=input.nextInt();
            }
        }
        dfs(x0,y0,0);
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if(matrixStep[i][j]==n*m){
                    System.out.println("-1");
                    return;
                }
                if(matrixStep[i][j]!=-1&&matrixStep[i][j]>maxStep)    
                    maxStep=matrixStep[i][j];
            }
        }
        System.out.println(maxStep);
    }
    
    public static void dfs(int x,int y,int count){
        int length;
        for(int i=0;i<k;i++){
            if(checkIndex(x+step[i][0],y+step[i][1])){
                if(checkPath(x,x+step[i][0],y,y+step[i][1])){
                    //使用回溯法
                    put(x,x+step[i][0],y,y+step[i][1],true);
                    length=count+1;
                    int temp=matrixStep[y+step[i][1]][x+step[i][0]];
                    if(temp==n*m||temp>length){
                        matrixStep[y+step[i][1]][x+step[i][0]]=length;
                    }else{
                        put(x,x+step[i][0],y,y+step[i][1],false);
                        continue;
                    }
                    dfs(x+step[i][0],y+step[i][1],length);
                    put(x,x+step[i][0],y,y+step[i][1],false);
                }
            }
        }
    }
    
    public static boolean checkIndex(int x,int y){
        return (0<=x&&x<m)&&(0<=y&&y<n)?true:false;
    }
    
    public static boolean checkPath(int x,int x0,int y,int y0){
        //如果所行路径不可通行返回false
        if(matrix[y0][x0]=='X')
            return false;
        else
            return true;
    }
    
    public static void put(int x,int x0,int y,int y0,boolean flag){
        //flag    true:put'X',false:put'.'
        if(flag)
            matrix[y0][x0]='X';
        else
            matrix[y0][x0]='.';
            
    }
}

	

一开始理解错题目怎么都不能ac，以为是迷宫问题，偷偷瞄了下答案，只要加个双重for 就可以修改得到答案

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    public static int BFS(boolean[][] maze,boolean[][] visit,int[] start,int[] end,int[][] dirs){
        Queue<int[]> queue = new LinkedList<>();
        int [] now,next;
        int [] node = new int []{start[0],start[1],0};
        queue.add(node);
        visit[start[0]][start[1]] = true;
        int maxStep = 0; //整个队列中走的步数最多的步数
        while (!queue.isEmpty()){
            now = queue.poll();
            //if (now[0] == end[0] && now[1] == end[1]) return now[2];
            if(maxStep < now[2]) maxStep = now[2];
            for(int[] dir:dirs){
                next = new int[]{dir[0]+now[0],dir[1]+now[1],now[2]+1};
                if (next[0]<0||next[0]>=maze.length || next[1] < 0|| next[1] >= maze[0].length
                        ||visit[next[0]][next[1]] == true||maze[next[0]][next[1]] == true){
                    continue;
                }
                queue.add(next);
                visit[next[0]][next[1]] = true;
            }
        }
        //有没走到的返回-1
        for (int i = 0;i < maze.length; i++){
            for (int j = 0;j < maze[0].length; j++){
                if (visit[i][j] ==false && maze[i][j] == false) return -1;
            }
        }

        return  maxStep;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            boolean[][] maze = new boolean[n][m];
            for(int i = 0; i < n; i++){
                String s = sc.next();
                for(int j = 0; j < m; j++){
                    if(s.charAt(j) != '.') maze[i][j] = true;
                }
            }
            int []start = new  int[]{sc.nextInt(),sc.nextInt()};
            int ndir = sc.nextInt();
            int [][] dirs = new int[ndir][2];
            for(int i = 0; i < ndir; i++){
                dirs[i][0] = sc.nextInt();
                dirs[i][1] = sc.nextInt();
            }
            boolean[][] visit = new boolean[n][m];
            System.out.println(BFS(maze,visit,start,new int[]{n-1,m-1},dirs));
        }
        sc.close();
    }
}

//在所有可访问的点中，找出到各点最小步数中最大的一个；如果有可到达的点最终却没有被访问，
那么输出-1。（利用BFS进行遍历）
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int row = in.nextInt(), col = in.nextInt();
            char[][] map = new char[row][col];
            int[][] record = new int[row][col];
            for (int i = 0; i < row; i++) {
                String string = in.next();
                map[i] = string.toCharArray();
            }
            int startX = in.nextInt(), startY = in.nextInt();
            int k = in.nextInt();
            int[] stepsX = new int[k];
            int[] stepsY = new int[k];
            for (int i = 0; i < k; i++) {
                stepsX[i] = in.nextInt();
                stepsY[i] = in.nextInt();
            }
            Queue<Integer> queueX = new LinkedList<>();
            Queue<Integer> queueY = new LinkedList<>();
            queueX.add(startX); queueY.add(startY);
            record[startX][startY] = 1;
            while (!queueX.isEmpty()) {
                startX = queueX.poll();
                startY = queueY.poll();
                for (int i = 0; i < k; i++) {
                    if (startX + stepsX[i] < 0 || startX + stepsX[i] >= row ||
                            startY + stepsY[i] < 0 || startY + stepsY[i] >= col)
                        continue;
                    if (record[startX+stepsX[i]][startY+stepsY[i]] == 0) {
                        //该点未访问过
                        if (map[startX+stepsX[i]][startY+stepsY[i]] == '.') {
                            record[startX+stepsX[i]][startY+stepsY[i]] = record[startX][startY] + 1;
                            queueX.offer(startX+stepsX[i]);
                            queueY.offer(startY+stepsY[i]);
                        } else
                            record[startX+stepsX[i]][startY+stepsY[i]] = -1;
                    }
                }
            }
            int res = 0;
            boolean isOk = true;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    //有点未被访问过
                    if (record[i][j] == 0 && map[i][j] == '.') {
                        isOk = false; break;
                    }
                    res = Math.max(res, record[i][j]);
                }
            }
            if (isOk) System.out.println(res-1);
            else System.out.println(-1);
        }
    }
}

//开心，刷题生涯中关于动态规划的题，第一次提交就过了

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他
 * 每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况
 * 下，他需要多少步才可以离开这个地牢。
 * 输入描述:
 * 每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，
 * 地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x0, y0，表示牛牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是
 *  '.'）。之后的一行包含一个整数 k（0 < k <= 50）表示牛牛合法的步长数，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx
 *  , dy <= 50）
 *  输出描述:
 *  输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出
 *  口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。
 *  示例1
 *  输入
3 3
...
...
...
0 1
4
1 0
0 1
-1 0
0 -1
 *  输出
 *  3
 * @author zhouyueyue
 *
 */
public class Main {
    static boolean test = false;

    class Loc{
        public int x;
        public int y;    
        public Loc() {
            // TODO Auto-generated constructor stub
        }
        public Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }
    public static void main(String[] args) {
        int n = 0, m = 0;
        char[][] diLao = null;
        int x0 = 0, y0 = 0;//初始化坐标
        int k = 0; //牛牛走法的种类
        int[][] d= null;
        Scanner in = new Scanner(System.in);
        int max = Integer.MAX_VALUE;
        while (in.hasNext()){

            n = in.nextInt();
            m =in.nextInt();
            diLao = new char[n][m];
            for(int i = 0; i < n; i++ ){
                String str = in.next();
                diLao[i] = str.toCharArray();
            }
            x0 = in.nextInt();
            y0 = in.nextInt();
            k = in.nextInt();
            d = new int[k][2];
            for(int i = 0; i < k; i++){
                d[i][0]  = in.nextInt();
                d[i][1] = in.nextInt();
            }
            int[][] F = new int[n][m];
            //diLao = initDiLao(n, m);//地牢初始化
            //d = initD(k);//走法矩阵初始化
            //初始化F，即结果数组
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    F[i][j] = max;
                }
            }
            LinkedList<Loc> queue = new LinkedList<>();
            F[x0][y0] = 0;
            queue.add(new Main().new Loc(x0, y0));

            while(!queue.isEmpty()){
                Loc loc = queue.poll();
//                nextStep(loc, d);
                for(int i = 0; i < k; i++){
                    int x = loc.x;
                    int y = loc.y;
                    int stepX = d[i][0];
                    int stepY = d[i][1];

                    int curX = x + stepX;
                    int curY = y + stepY;
                    if(curX >= 0 && curY >= 0 && curX < n && curY < m){
                        if(diLao[curX][curY] != 'X'){
                            F[curX][curY] = Math.min(F[x][y] + 1, F[curX][curY]);
                        }    
                        if(F[x][y] + 1 <= F[curX][curY] && diLao[curX][curY] != 'X'){
                            queue.add(new Main().new Loc(curX, curY));

                        }
                        //res = Math.max(res, F[curX][curY]);
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if(diLao[i][j] != 'X'){
                        res = Math.max(res, F[i][j]);
                    }
                }
            }
            if(res == max){
                System.out.println(-1);
            }else{
                System.out.println(res);
            }
        }

    }
}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main{
	static class Point {
		int x;
		int y;
		int d;
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
		Point(int x, int y, int d){
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	public static void main(String[] args){
    	Scanner in = new Scanner(System.in);
    	while(in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            char[][] maz = new char[n][m];
            int[][] book = new int[n][m];
            // eat the \n
            in.nextLine();
            for(int i = 0; i < n; i ++) {
            	String str = in.nextLine();
            	maz[i] = str.toCharArray();
            	for(int j = 0; j < m; j ++) {
            		if(maz[i][j] == 'X') {
                		book[i][j] = 1;            			
            		}
            	}
            }
            int x0 = in.nextInt();
            int y0 = in.nextInt();
            int k = in.nextInt();
            int[] dx = new int[k];
            int[] dy = new int[k];
            for(int i = 0; i < k; i ++) {
            	dx[i] = in.nextInt();
            	dy[i] = in.nextInt();
            }
            int result = BFS(maz, book, n, m, dx, dy, new Point(x0, y0));
            System.out.println(result);
    	}
    }
	
	public static int BFS(char[][] maz, int[][] book, int n, int m, int[] dx, int[] dy, Point start) {
		Queue<Point> queue = new LinkedList<Point>();
		queue.offer(start);
		book[start.x][start.y] = 1;
		int steps = 0;
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			steps = p.d > steps ? p.d: steps;
			for(int i = 0; i < dx.length; i ++) {
				for(int j = 0; j < dx.length; j ++) {
					int x = p.x + dx[i];
					int y = p.y + dy[i];
					if(0 <= x && x < n && 0 <= y && y < m && maz[x][y] == '.' && book[x][y] == 0) {
						book[x][y] = 1;
						queue.offer(new Point(x, y, p.d + 1));
					}
				}
			}
		}
		// check if there are any points unreachable;
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				if(book[i][j] == 0) {
					return -1;
				}
			}
		}
		return steps > 0? steps: -1;		
	}
}