Submission

Score: 0

User: theem1502

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

Language: cpp

Time: 1.089 second

Submitted On: 2026-02-19 21:35:14

#include <bits/stdc++.h>
using namespace std;
int row, collumn;
int dix[9] = {0,0,-1,1,0,1,1,-1,-1};
int diy[9] = {1,-1,0,0,0,1,-1,1,-1};
const int INF = 1e9;
int bfs(int startx, vector<vector<bool>> &realarray, vector<vector<int>> &visited, int key) {
    queue<pair<int,int>> theq;
    theq.push(make_pair(startx, 0));
    int count = 0;
    while(!theq.empty()) {

    int thesize = theq.size();
    for (int i = 0; i < thesize; i++) {

        int currentx = theq.front().first, currenty = theq.front().second;
        theq.pop();
        if (visited[currentx][currenty] == key) {
            continue;
        }
        visited[currentx][currenty] = key;
        if (currenty == collumn - 1) {
            return count + 1;
        }
        for (int j = 0; j < 4; j++) {
            int newx =currentx + dix[j] , newy = currenty + diy[j];
            if (newx < 0 || newy  < 0 || newx >= row || newy >= collumn){
                continue;
            }
            if (realarray[newx][newy]) {
                continue;
            }
            theq.push({newx, newy});
        }

        }

        count++;

    }
    return INF;
}

int main() {

    cin >> row >> collumn;
    vector<vector<int>> thearray(row, vector<int> (collumn));
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < collumn; j++) {
        cin >> thearray[i][j];
        }
    }

    vector<vector<bool>> realarray(row, vector<bool> (collumn,false));

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < collumn; j++) {
            if (thearray[i][j] == 0) {
                for (int k = 0; k < 9; k++) {
                    int newi = i + dix[k], newj = j + diy[k];
                    if (newi < 0 || newj < 0 || newi >= row || newj >= collumn) {
                        continue;
                    }
                    realarray[newi][newj] = true;
                }
            }
        }
    }
    /*
    for (int j = 0; j < row; j++) {
            for (int k = 0; k < collumn; k++) {
                cout << realarray[j][k] << " ";
            }
            cout << "\n";
        }
*/
    int best = INF;
    vector<vector<int>> visited(row, vector<int> (collumn));
    for (int i = 0; i < row; i++) {
           // cout << "here";
        if (realarray[i][0]) {
            continue;
        }
        best = min(best, bfs(i, realarray, visited, i+1));
       //visited.fill(0);
       /*
        for (int j = 0; j < row; j++) {
            for (int k = 0; k < collumn; k++) {
                visited[j][k] = 0;
            }
        }
        */
    }

    if (best == INF) {
        cout << -1;
        return 0;
    }
    cout << best;
}