提出 #64545743

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;
#define int long long

void dfs(vector<vector<char>>& arr, int i, int j) {
    int n = arr.size(), m = arr[0].size();
    if(i < 0 || j < 0 || i >= n || j >= m
        || arr[i][j] == '#' || arr[i][j] == 'T') return;

    arr[i][j] = 'T';
    dfs(arr, i+1, j);
    dfs(arr, i-1, j);
    dfs(arr, i, j+1);
    dfs(arr, i, j-1);
}

int bfs(vector<vector<char>>& arr, int dx, int dy) {
    queue<pair<int, pair<int,int>>> q;
    q.push({0, {dx, dy}});
    vector<int> dirx{-1, 0, 1, 0}, diry{0, -1, 0, 1};
    int n = arr.size(), m = arr[0].size();
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    int ans = LLONG_MAX;

    while(!q.empty()) {
        int i = q.front().second.first, j = q.front().second.second;
        int dist = q.front().first;
        // cout<<i<<' '<<j<<' '<<dist<<' '<<arr[i][j]<<endl;
        // if(arr[i][j] == 'T') return ceil(dist/2);
        q.pop();

        for(int k=0;k<4;k++) {
            int ti = dirx[k] + i, tj = diry[k] + j;
            if(ti < 0 || tj < 0 || ti >= n || tj >= m || vis[ti][tj]) continue;
            vis[ti][tj] = true;

            if(arr[ti][tj] == 'T') {
                ans = min((dist + 1) / 2, ans);
                continue;
            }
            if(arr[ti][tj] == '#') q.push({dist + 1, {ti, tj}});
            else q.push({dist, {ti, tj}});
        }

    }

    return ans;
}

signed main() {
    int n, m, sx, sy, dx, dy; cin>>n>>m;

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

    cin>>sx>>sy>>dx>>dy;
    sx--, sy--, dx--, dy--;
    dfs(arr, sx, sy);
    cout<<bfs(arr, dx, dy)<<endl;



    return 0;
}

提出情報

ジャッジ結果