题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

注意：A、B不一定是两个不同的点。

思路

从A处向四边走，不需要回溯。
到达B出就输出。

代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e2 + 5 ;

bool f ;
int n , m ;
char g[N][N] ;
int xa , xb , yb , ya ;
int dx[5] = { 0 , 1 , -1 , 0 , 0 } ;
int dy[5] = { 0 , 0 , 0 , 1 , -1 } ;

void dfs ( int x , int y ) {

    g[x][y] = '#' ;

    if ( x == xb && y == yb ) {

        cout << "YES" << endl ;
        f = true ; // 如果走到就设为真，如果到不了f不会为真 
        return ;

    }

    for ( int i = 1 ; i <= 4 ; i ++ ) {

        int nx = dx[i] + x ;
        int ny = dy[i] + y ;

        if ( g[nx][ny] == '.' ) {

            g[nx][ny] = '#' ;
            dfs ( nx , ny ) ;

        }

    }

}

int main ( ) {

    cin >> m ;
    while ( m -- ) {

        f = false ;
        memset ( g , '0' , sizeof ( g ) ) ;

        cin >> n ;
        for ( int i = 0 ; i < n ; i ++ )
            for ( int j = 0 ; j < n ; j ++ )
                cin >> g[i][j] ;

        cin >> xa >> ya >> xb >> yb ;

        if ( g[xa][ya] == '#' || g[xb][yb] == '#' ) {

            cout << "NO" << endl ;
            continue ;

        }

        dfs ( xa , ya ) ;

        if ( !f ) cout << "NO" << endl ; 

    }

    return 0 ;

}