_Dayao_ @ 2024-12-14 17:12:46

#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0;
bool b[1001][1001]={0},c=0;
char a[1001][1001];
void dfs(int x,int y){
    if(a[x][y]=='#')return;
    if(x==n&&y==m&&c==0){
        c=1;
        return;
    }
    if(b[x+1][y]==0&&a[x+1][y]=='.'){
        b[x][y]=1;
        dfs(x+1,y);
        b[x][y]=0;
    }
    if(b[x-1][y]==0&&a[x-1][y]=='.'){
        b[x][y]=1;
        dfs(x-1,y);
        b[x][y]=0;
    }
    if(b[x][y-1]==0&&a[x][y-1]=='.'){
        b[x][y]=1;
        dfs(x,y-1);
        b[x][y]=0;
    }
    if(b[x][y+1]==0&&a[x][y+1]=='.'){
        b[x][y]=1;
        dfs(x,y+1);
        b[x][y]=0;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>a[i][j];
    }
    dfs(1,1);
    if(!c)cout<<"No";
  if(c)cout<<"Yes";
}

by LMR_Minecraft @ 2024-12-14 17:23:59

额...怎么会TLE?

by LMR_Minecraft @ 2024-12-14 17:25:16

@ycl220038这程序不至于TLE吧?

by LG_jyc @ 2024-12-14 17:25:58

@ycl220038

把所有b[x][y]=0;的语句删掉试试

by kjq0409 @ 2024-12-14 17:30:08

第8行代码范围判断不用&&，用|| 帮你试过了，60分

by LMR_Minecraft @ 2024-12-14 17:33:59

@ycl220038我程序过了:

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct Point {
    int x, y;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<char>> maze(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> maze[i][j];
        }
    }

    // Directions: up, down, left, right
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    queue<Point> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    q.push({0, 0});
    visited[0][0] = true;

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        if (current.x == n - 1 && current.y == m - 1) {
            cout << "Yes";
            return 0;
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nx = current.x + dx[dir];
            int ny = current.y + dy[dir];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && maze[nx][ny] == '.') {
                q.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }

    cout << "No";
    return 0;
}

by LMR_Minecraft @ 2024-12-14 17:34:48

@ycl220038我AC了

by _Dayao_ @ 2024-12-14 19:02:23

@LMR_Minecraft 必须玄关

by _Dayao_ @ 2024-12-14 19:02:44

@LG_jyc 已关

by _Dayao_ @ 2024-12-14 19:03:05

@kjq0409 已关

by _Dayao_ @ 2024-12-14 19:10:56

@LG_jyc 要回溯，没学过深搜吗？