题目描述

给定一个方阵，定义连通：上下左右相邻，并且值相同。
可以想象成一张地图，不同的区域被涂以不同颜色。
输入：
整数N, (N<50)表示矩阵的行列数
接下来N行，每行N个字符，代表方阵中的元素
接下来一个整数M，(M<1000)表示询问数
接下来M行，每行代表一个询问，
格式为4个整数，y1,x1,y2,x2，
表示(第y1行,第x1列) 与 (第y2行,第x2列) 是否连通。
连通输出true，否则false
例如：
10
0010000000
0011100000
0000111110
0001100010
1111010010
0000010010
0000010011
0111111000
0000010000
0000000000
3
0 0 9 9
0 2 6 8
4 4 4 6

程序应该输出：
false
true
true

思路：

这道题目应该使用DFS来解决，这里区分一下图的DFS和BFS。图的DFS还是和树的DFS一样，一条路走到黑，而图的BFS则是遍历当前节点的每一个邻居，遍历完成后遍历下一个节点的所有邻居。

所以这道题目最好采用DFS来解决。图与树不一样，它在递归的过程中搜索到下一层的时候会回到上一层又进行相同的递归那么这样就会在递归中一直出不去造成死循环，所以在这里进行深搜需要加上当前节点是否被访问的标志当进入下一次的递归的时候如果上一次的节点被标记过那么就不会再回来进行相同的递归了。

还有就是当退回到当前状态的时候需要进行回溯，因为我们在访问之后有可能当前的节点走下去是不符合的，所以需要把之前访问过的痕迹清除掉以便在下次尝试其它路径的时候能够访问到当前的节点。

java 代码

import java.util.Scanner;

public class Main {

    static int dirx[]= {0,0,-1,1};
    static int diry[]= {-1,1,0,0};
    static int n;

    public static boolean dfs(char[][] graph,int[][] flag, int[] str) {
        int x1=str[0];
        int y1=str[1];
        int x2=str[2];
        int y2=str[3];

        if(x1==x2 && y1==y2) {
            return true;
        }

        boolean f1=false;
        boolean f2=false;
        boolean f3=false;
        boolean f4=false;
            //左
            int newx=x1+dirx[0];
            int newy=y1+diry[0];
            if(newx>=0 && newx<graph.length && newy>=0 && newy<graph.length && graph[newx][newy]==graph[x1][y1] && flag[newx][newy]==0) {
                flag[newx][newy]=1;
                str[0]=newx;
                str[1]=newy;    
                f1=dfs(graph,flag,str);
                flag[newx][newy]=0;
                str[0]=x1;
                str[1]=y1;          
            }

            //右
            newx=x1+dirx[1];
            newy=y1+diry[1];
            if(newx>=0 && newx<graph.length && newy>=0 && newy<graph.length && graph[newx][newy]==graph[x1][y1] && flag[newx][newy]==0) {
                flag[newx][newy]=1;
                str[0]=newx;
                str[1]=newy;    
                f2=dfs(graph,flag,str);
                flag[newx][newy]=0;
                str[0]=x1;
                str[1]=y1;          
            }

            //上
            newx=x1+dirx[2];
            newy=y1+diry[2];
            if(newx>=0 && newx<graph.length && newy>=0 && newy<graph.length && graph[newx][newy]==graph[x1][y1] && flag[newx][newy]==0) {
                flag[newx][newy]=1;
                str[0]=newx;
                str[1]=newy;    
                f3=dfs(graph,flag,str);
                flag[newx][newy]=0;
                str[0]=x1;
                str[1]=y1;          
            }

            //下
            newx=x1+dirx[3];
            newy=y1+diry[3];
            if(newx>=0 && newx<graph.length && newy>=0 && newy<graph.length && graph[newx][newy]==graph[x1][y1] && flag[newx][newy]==0) {
                flag[newx][newy]=1;
                str[0]=newx;
                str[1]=newy;    
                f4=dfs(graph,flag,str);
                flag[newx][newy]=0;
                str[0]=x1;
                str[1]=y1;          
            }
        return f1 || f2 || f3 || f4;    //false

}

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        sc.nextLine();
        char[][] graph = new char[n][n];
        for(int i=0;i<n;i++) {
            graph[i]=sc.nextLine().toCharArray();
        }
        int m=sc.nextInt();
        int[][] a=new int[m][4];
        for(int i=0;i<1;i++) {
            for(int j=0;j<4;j++) {
                a[i][j]=sc.nextInt();           
            }       
        }
        for(int i=0;i<m;i++) {              
            System.out.println(dfs(graph,new int[n][n],a[i]));
        }
    }


}