90TLE求调
查看原帖
90TLE求调
1342124
wangrongze楼主2025/5/16 16:42
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 120;
constexpr int dx[] = {0, 1, 0, -1};
constexpr int dy[] = {1, 0, -1, 0};
char grid[N][N];
int n, m, a[N][N], xx[N*N], yy[N*N]; 
bool vis[N][N], f;
bool check(int x, int y){
    return x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] && !vis[x][y];
}
void print(int step){
    for(int i = 1; i <= step; i++){ 
        cout << xx[i] << ' ' << yy[i] << '\n';
    }
    f = true;
}
void dfs(int x, int y, int step){
    if(!check(x, y) || step > (int)1e5) return; 
    vis[x][y] = true;
    xx[step] = x;
    yy[step] = y;
    if(x == n && y == m){
        print(step);
        return ;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(check(nx, ny)) dfs(nx, ny, step + 1);
        if(f) return ;
    }
    vis[x][y] = false; 
    return ;
}
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> grid[i][j];
            if(grid[i][j] == '*') a[i][j] = 0; 
            else a[i][j] = 1; 
        }
    }
    dfs(1, 1, 1);
    return 0;
}
2025/5/16 16:42
加载中...