oj.uz

답안 #895975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895975 2023-12-31T09:11:31 Z niter Maze (JOI23_ho_t3) C++14
0 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define BAE(x) (x).begin(), (x).end()
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }

inline bool check(int i, int j, int n, int m){
    return i >= 0 && j >= 0 && i < n && j < m;
}
const int INF = (int)(1e9);
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<pii> dr;
vector<vector<char>> c;
vector<vector<int>> dis;
vector<vector<bool>> special;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, L;
    cin >> n >> m >> L;
    pii s, t;
    cin >> s.ff >> s.ss >> t.ff >> t.ss;
    s.ff--; s.ss--; t.ff--; t.ss--;
    c = vector<vector<char>>(n, vector<char>(m, ' '));
    loop(i,0,n){
        loop(j,0,m){
            cin >> c[i][j];
        }
    }
    for(int i = -1; i <= 1; i += 2){
        for(int j = -1; j <= 1; j += 2){
            dr.pb({L * i, L * j});
            for(int k = 0; k < L; k ++){
                dr.pb({k * i, (L + 1) * j});
                dr.pb({(L + 1) * j, k * i});
            }
        }
    }
    sort(BAE(dr));
    dr.resize(unique(BAE(dr)) - dr.begin());
//    STL(dr);
    special = vector<vector<bool>>(n, vector<bool>(m, false));
    for(auto &i:dr){
        int nx = s.ff + i.ff;
        int ny = s.ss + i.ss;
        if(check(nx, ny, n, m)){
            special[nx][ny] = true;
        }
    }
    dis = vector<vector<int>>(n, vector<int>(m, INF));
    dis[s.ff][s.ss] = 0;
    queue<pii> Q;
    Q.push(s);
    while(!Q.empty()){
        int nowx = Q.front().ff;
        int nowy = Q.front().ss;
        Q.pop();
        if(special[nowx][nowy]) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(dis[nx][ny] == INF){
                dis[nx][ny] = 1;
                Q.push({nx, ny});
            }
        }
    }
    priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq;
    loop(i,0,n){
        loop(j,0,m){
            if(c[i][j] == '#') dis[i][j] = INF;
            if(dis[i][j] != INF) pq.push({dis[i][j], {i, j}});
        }
    }
//    pq.push({0, s});
    while(!pq.empty()){
        int nowx = pq.top().ss.ff;
        int nowy = pq.top().ss.ss;
        int nowd = pq.top().ff;
        pq.pop();
        if(nowd != dis[nowx][nowy]) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(c[nx][ny] == '#') continue;
            if(dis[nx][ny] > nowd){
                dis[nx][ny] = nowd;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
        for(auto &d:dr){
            int nx = nowx + d.ff;
            int ny = nowy + d.ss;
            if(!check(nx, ny, n, m)) continue;
            if(c[nx][ny] == '#') continue;
            if(dis[nx][ny] > nowd + 1){
                dis[nx][ny] = nowd + 1;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
    }
    cout << dis[t.ff][t.ss] << '\n';
}
/*
*/

Compilation message

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
Main.cpp:17:86: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }
      |                                                                                      ^

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 0 ms 460 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -