Submission

Score: 0

User: Regent

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

Language: cpp

Time: 0.009 second

Submitted On: 2026-03-05 15:41:43

#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 && !visited[ni][nj]){
            grid[ni][nj] = 0;
            visited[ni][nj] = true;
        }
    }
}
//
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(ex == i && ey == j){
            return dist[i][j];
        }

        for(auto [x,y] : delta){
            int ni = x + i;
            int nj = y + j;
            if(ni >= 0 && ni < n && nj >= 0 && nj < m && !visited[ni][nj] && grid[ni][nj] == 1){
                q.push({ni,nj});
                visited[ni][nj] = true;
                dist[ni][nj] = dist[i][j] + 1;
            }
        }
    }
    return -1;
}
//
int main(){
    Kana;

    int n,m;
    cin >> n >> m;
    vector<vector<int>> grid(n,vector<int>(m));
    vector<vector<int>> ans;
    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 && !visited[i][j]){
                makefalse(i,j,grid,n,m);
            }
        }
    }
    //
    vector<pair<int,int>> starts;
    for(int i = 0;i < m;i++){
        if(grid[i][0] != 0){
            starts.push_back({i,0});
        }
    }
    vector<pair<int,int>> ends;
    for(int i = 0;i < m;i++){
        if(grid[i][m-1] != 0){
            ends.push_back({i,m-1});
        }
    }
    int mn = INT_MAX;
    vector<int> a;
    for(auto [sx,sy] : starts){
        for(auto [ex,ey] : ends){
            memset(dist,false,sizeof(dist));
            memset(visited,false,sizeof(visited));
            int u = bfs(sx,sy,ex,ey,grid,n,m);
            mn = min(mn,u);
            a.push_back(u);
        }
    }
    
    /*
    cout << "----------------------------------------------------------------------\n";
    for(auto &x : a){
        cout << x << '\n';
    }
    cout << "----------------------------------------------------------------------\n";
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << grid[i][j] << " ";
        }cout << '\n';
    }
    cout << "----------------------------------------------------------------------\n";
    cout << "START\n";
    for(auto [x,y] : starts){
        cout << x << " " << y << '\n';
    }
    cout << "----------------------------------------------------------------------\n";
    cout << "End\n";
    for(auto [x,y] : ends){
        cout << x << " " << y << '\n';
    }
    */

    cout << (mn == INT_MAX ? -1 : mn + 1);
    return 0;
}