题目描述
迷宫包含n行m列个小方格，0表示可通行，1表示不可通行。在迷宫的某一位置只能向东南西北四个方向移动。 问题：判断迷宫两点之间是否有路径
输入
第一行为n和m，逗号分隔 从第2行到第1+n行，每行一个由0和1组成的长度为m的字符串，代表迷宫的结构 第2+n行 数字k，代表要判断的点对个数 第3+n行到2+n+2k行，每行一个坐标代表点
输出
按照顺序判断点对是否可达，输出true或者false
样例输入
4 15 110001001111110 101001111101111 010100011101111 111101000000001 4 1 3 3 7 1 7 1 8 1 7 3 7 4 5 4 7
样例输出
true true false true
代码实现
import java
.util
.Scanner
;
public class Main {
int n
,m
,row1
,row2
,line1
,line2
;
int k
;
char[][]A
;
int []dx
,dy
;
String
[]result
;
public Main(){
dx
=new int[]{-1,1,0,0};
dy
=new int[]{0,0,-1,1};
Scanner sc
=new Scanner(System
.in
);
n
=sc
.nextInt();
m
=sc
.nextInt();
A
=new char[n
][m
];
for(int i
=0;i
<n
;i
++){
String s
=sc
.next();
for(int j
=0;j
<m
;j
++){
A
[i
][j
]=s
.charAt(j
);
}
}
k
=sc
.nextInt();
result
=new String[k
];
for(int t
=0;t
<k
;t
++){
row1
=sc
.nextInt()-1;
line1
=sc
.nextInt()-1;
row2
=sc
.nextInt()-1;
line2
=sc
.nextInt()-1;
for(int i
=row1
;i
<n
;i
++){
for(int j
=line1
;j
<m
;j
++)
if(A
[i
][j
]=='0')
Search(i
,j
);
result
[t
]=(A
[row2
][line2
]=='2'?"true":"false");
break;
}
for(int i
=0;i
<n
;i
++){
for(int j
=0;j
<m
;j
++)
if(A
[i
][j
]=='2')
A
[i
][j
]='0';
}
}
for(int i
=0;i
<k
;i
++){
System
.out
.println(result
[i
]);
}
}
void Search(int x
,int y
){
A
[x
][y
]='2';
for(int a
=0;a
<4;a
++){
int tx
=x
+dx
[a
],ty
=y
+dy
[a
];
if(tx
>=0 && tx
<n
&& ty
>=0 && ty
<m
&&A
[tx
][ty
]=='0')
Search(tx
,ty
);
}
}
public static void main(String args
[]){
Main c
=new Main();
}
}
