Submission

Score: 0

User: Regent

Problemset: ย่องเบาหลบกับระเบิด

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-05 15:51:37

#include<bits/stdc++.h>
#define Kana ios_base::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;

vector<pair<int,int>> d = {{-1,-1},{1,-1},{-1,1},{1,1},{0,1},{0,-1},{1,0},{-1,0}};
vector<pair<int,int>> delta = {{0,1},{0,-1},{1,0},{-1,0}};

bool visited[1000][1000];
int dist[1000][1000];

void makefalse(int &i,int &j,vector<vector<int>> &grid,int &n,int &m){
    for(auto [x,y] : d){
        int ni = x + i;
        int nj = y + j;
        if(ni >= 0 && nj >= 0 && ni < n && nj < m){
            grid[ni][nj] = 0;
        }
    }
}

int bfs(int sx,int sy,int ex,int ey,vector<vector<int>> &grid,int n,int m){
    queue<pair<int,int>> q;
    if(grid[sx][sy] == 0) return -1;
    if(grid[ex][ey] == 0) return -1;
    q.push({sx,sy});
    visited[sx][sy] = true;
    dist[sx][sy] = 0;
    while(!q.empty()){
        auto [i,j] = q.front();
        q.pop();
        if(i == ex && j == ey) return dist[i][j];
        for(auto [x,y] : delta){
            int ni = i + x;
            int nj = j + y;
            if(ni >= 0 && ni < n && nj >= 0 && nj < m &&
               !visited[ni][nj] && grid[ni][nj] == 1){
                visited[ni][nj] = true;
                dist[ni][nj] = dist[i][j] + 1;
                q.push({ni,nj});
            }
        }
    }
    return -1;
}

int main(){
    Kana;

    int n,m;
    cin >> n >> m;

    vector<vector<int>> grid(n,vector<int>(m));

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> grid[i][j];
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(grid[i][j] == 0){
                makefalse(i,j,grid,n,m);
            }
        }
    }
    vector<pair<int,int>> starts;
    for(int i = 0;i < n;i++){
        if(grid[i][0] == 1){
            starts.push_back({i,0});
        }
    }
    vector<pair<int,int>> ends;
    for(int i = 0;i < n;i++){
        if(grid[i][m-1] == 1){
            ends.push_back({i,m-1});
        }
    }
    int mn = INT_MAX;
    for(auto [sx,sy] : starts){
        for(auto [ex,ey] : ends){
            memset(dist,0,sizeof(dist));
            memset(visited,false,sizeof(visited));
            int u = bfs(sx,sy,ex,ey,grid,n,m);
            if(u != -1)
                mn = min(mn,u);
        }
    }
    cout << (mn == INT_MAX ? -1 : mn + 1);
    return 0;
}