제출 #1256885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256885		christhegamechanger	장애물 (IOI25_obstacles)	C++17	0 / 100	2106 ms	211084 KiB

obstacles

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int N, M;
vector<int> T, H;

void initialize(vector<int> temp, vector<int> hum) {
    N = temp.size();
    M = hum.size();
    T = temp;
    H = hum;
}

bool can_reach(int L, int R, int S, int D) {
    if (S == D) return true;
    
    map<pair<int,int>, bool> visited;
    queue<pair<int,int> > Q;
    
    Q.push(make_pair(0, S));
    visited[make_pair(0, S)] = true;
    
    while (!Q.empty()) {
        pair<int,int> cur = Q.front();
        Q.pop();
        
        int row = cur.first;
        int col = cur.second;
        
        if (row == 0 && col == D) {
            return true;
        }
        
        // up
        if (row > 0) {
            int nrow = row - 1;
            int ncol = col;
            if (ncol >= L && ncol <= R && T[nrow] > H[ncol]) {
                pair<int,int> next = make_pair(nrow, ncol);
                if (visited.find(next) == visited.end()) {
                    visited[next] = true;
                    Q.push(next);
                }
            }
        }
        
        // down
        if (row < N - 1) {
            int nrow = row + 1;
            int ncol = col;
            if (ncol >= L && ncol <= R && T[nrow] > H[ncol]) {
                pair<int,int> next = make_pair(nrow, ncol);
                if (visited.find(next) == visited.end()) {
                    visited[next] = true;
                    Q.push(next);
                }
            }
        }
        
        // left
        if (col > L) {
            int nrow = row;
            int ncol = col - 1;
            if (T[nrow] > H[ncol]) {
                pair<int,int> next = make_pair(nrow, ncol);
                if (visited.find(next) == visited.end()) {
                    visited[next] = true;
                    Q.push(next);
                }
            }
        }
        
        // right
        if (col < R) {
            int nrow = row;
            int ncol = col + 1;
            if (T[nrow] > H[ncol]) {
                pair<int,int> next = make_pair(nrow, ncol);
                if (visited.find(next) == visited.end()) {
                    visited[next] = true;
                    Q.push(next);
                }
            }
        }
    }
    
    return false;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17