算法提高课汇总

算法思路

$dfs$与$bfs$都能求解连通性问题 — 分为最短路模型和最小步数模型.

本题属于最短路模型, 用$dfs$解决与$bfs$实现相比:

• $dfs$只能求出图内两点是否联通, 无法保证是最短路径.

• 因为系统实现了stack, 相比于$bfs$需要我们自己实现queue, $dfs$的代码更短.

• 两者实现复杂度相同: 判重数组保证每个点只会被遍历一次, 线性时间.

具体实现

注意:

• $dfs$实现时特别需要注意是否会爆栈的问题, 系统栈一般默认为$1M$. 最简单的判断方式是 — 实践出真知.

#include <cstring>
#include <iostream>

using namespace std;

const int N = 110;

int n;
char g[N][N];
bool st[N][N];
int xa, ya, xb, yb;

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

bool dfs(int x, int y)
{
    if( g[x][y] == '#' )    return false;
    if( x == xb && y == yb )    return true;

    st[x][y] = true;
    for( int i = 0; i < 4; i ++ )
    {
        int nx = x + dx[i], ny = y + dy[i];
        if( nx < 0 || nx >= n || ny < 0 || ny >= n )    continue;
        if( st[nx][ny] )  continue;

        if( dfs(nx, ny) )   return true;
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while ( T -- )
    {
        cin >> n;
        for( int i = 0; i < n; i ++ )   cin >> g[i];
        cin >> xa >> ya >> xb >> yb;

        memset(st, 0, sizeof st);
        if( dfs(xa, ya) )   puts("YES");
        else    puts("NO");
    }
    return 0;
}