蓝桥-深度优先求连通性

柔光的暖阳◎ 2022-04-12 13:43 189阅读 0赞

给定一个方阵，定义连通：上下左右相邻，并且值相同。  
可以想象成一张地图，不同的区域被涂以不同颜色。  
输入：  
整数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

import java.util.Scanner;
    
    public  class Lian_tong {
    public static boolean lian_tong(char[][]data,int x1,int y1,int x2,int y2) {
    if(x1==x2&&y1==y2)
    return true;
    char old=data[x1][y1];
    //避免又回到原来，对访问过的点进行标记
    data[x1][y1]='*';
    try {
    if(x1<data.length-1&&data[x1+1][y1]==old&&lian_tong(data,x1+1,y1,x2,y2)) {
    return true;
    }
    if(y1<data.length-1&&data[x1][y1+1]==old&&lian_tong(data,x1,y1+1,x2,y2)) {
    return true;
    }
    if(x1>0&&data[x1-1][y1]==old&&lian_tong(data,x1-1,y1,x2,y2)) {
    return true;
    }
    if(y1>0&&data[x1][y1-1]==old&&lian_tong(data,x1,y1-1,x2,y2)) {
    return true;
    }	
    }
    finally {
    data[x1][y1]=old;
    }
    return false;	
    }
    
    public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    //n:矩阵的行列式
    int n=Integer.parseInt(sc.nextLine());
    //输入n行n列，用二维数组接收
    char [][] data=new char[n][];
    for(int i=0;i<n;i++){
    data[i]=sc.nextLine().toCharArray();
    }
    //计算n次是否连通
    int m=Integer.parseInt(sc.nextLine());
    for(int i=0;i<m;i++) {
    String []s=sc.nextLine().split(" ");
    int x1=Integer.parseInt(s[0]);
    int y1=Integer.parseInt(s[1]);
    int x2=Integer.parseInt(s[2]);
    int y2=Integer.parseInt(s[3]);
    System.out.println(lian_tong(data,x1,y1,x2,y2));
    }	
    }
    }