You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
const int INF = 0x3f3f3f3f ;
const int N = 51 ;
int n , m ; // n行m列
int hax , hay ; //小哈所在的位置
int hengx , hengy ; //小哼开始的位置
int Min = INF ; //步骤最小值
int a [ N ] [ N ] ; //地图
bool st [ N ] [ N ] ; //是否走过
/**
测试数据
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1
4 3
*/
void dfs ( int x , int y , int step ) {
int dx [ 4 ] = { 0 , 1 , 0 , - 1 } ; //上,右，下，左
int dy [ 4 ] = { 1 , 0 , - 1 , 0 } ;
int tx , ty , k ;
//判断是否到达小哈的位置
if ( x = = hax & & y = = hay ) {
if ( step < Min ) Min = step ; //更新最小值
return ;
}
/*枚举四种走法*/
for ( k = 0 ; k < = 3 ; k + + ) {
/*计算下一个点的坐标*/
tx = x + dx [ k ] ;
ty = y + dy [ k ] ;
if ( tx < 1 | | tx > n | | ty < 1 | | ty > m ) //判断是否越界
continue ;
/*判断该点是否为障碍物或者已经在路径中*/
if ( ! a [ tx ] [ ty ] & & ! st [ tx ] [ ty ] ) {
st [ tx ] [ ty ] = true ; //标记这个点已经走过
dfs ( tx , ty , step + 1 ) ; //开始尝试下一个点
st [ tx ] [ ty ] = false ; //尝试结束，取消这个点的标记
}
}
}
int main ( ) {
cin > > n > > m ;
/*读入迷宫*/
for ( int i = 1 ; i < = n ; i + + )
for ( int j = 1 ; j < = m ; j + + ) cin > > a [ i ] [ j ] ;
//读入起点和终点坐标
cin > > hengx > > hengy > > hax > > hay ;
/*从起点开始搜索*/
st [ hengx ] [ hengy ] = true ; //标记起点已经在路径中，防止后面重复走
//第一个参数是起点的x坐标， ，
dfs ( hengx , hengy , 0 ) ;
//输出最短步数
cout < < Min < < endl ;
return 0 ;
}
