题目可以转换成 "能否找到两条从起点到终点无重复格子的路径（起点和终点可以重复）"。

可以写个记忆化搜索，搜索两次，第一次搜索后把第一次的路径除了起点和终点标记为 墙。然后再搜索一次看看有没有第二条路径。如果有则"YES" 否则 "NO"

具体看代码 时间复杂度 O(N)



#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e6 + 10;
int dp[4][N];
bool v[4][N];//为 true说明这个点没有路径可以继续往下走到终点

bool dfs(int x,int y){
    if(x > n || y > 3){
        cout << "fds " << " " << x << " " << y << 
           endl;
        return 0;
    }
    if(x == n && y == 3)
        return 1;
    if(v[y][x]) return 0;//已经确定在这个点没有路径

    if(x < n && dp[y][x + 1] == 0)//向下走能走且不是墙
    {
        dp[y][x + 1] = 1;//标记这个点为路径上的点
        if(dfs(x + 1,y))//找到路径
            return 1;
        v[y][x + 1] = 1;// 标记这个点没有路径
        dp[y][x + 1] = 0;//这个点没有路径，取消标记
    }
     if(y < 3 && dp[y + 1][x] == 0)//向右走能走且不是墙
    {
        dp[y + 1][x] = 1;//标记这个点为路径上的点
        if(dfs(x,y + 1))//找到路径
            return 1;
         v[y + 1][x] = 1;// 标记这个点没有路径
        dp[y + 1][x] = 0;//这个点没有路径，取消标记
    }
    return 0;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x,y;    cin >> y >> x;
        dp[y][x] = 1;//标记墙
    }

    if(dfs(1,1)){//第一次可以找到路径
        dp[1][1] = dp[3][n] = 0;
        memset(v,0,sizeof v);
        if(dfs(1,1))//第二次也能找到路径
        {     cout << "YES" ; return 0; }

    }
        cout << "NO" ;
    return 0;
}