제출 #1186759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186759		pxsit	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	198 ms	20296 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int h, w; 
vector<string> adj; 
vector<vector<bool>> visited; 


bool is_valid(int r, int c) {
    return r >= 0 && r < h && c >= 0 && c < w;
}

bool bfs(char t) {
    if (adj[0][0] != t) {
        return false; 
    }
    queue<pair<int, int>> q;
    visited.assign(h, vector<bool>(w, false)); 
    q.push({0, 0});
    visited[0][0] = true; 
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop(); 
        int y = curr.first; 
        int x = curr.second; 
        if (y == h - 1 && x == w - 1) {
            return true; 
        }
        for (int i = 0; i < 4; i++) {
            int ny = y + dx[i]; 
            int nx = x + dy[i]; 
            if (is_valid(ny, nx) && adj[ny][nx] == t && !visited[ny][nx]) {
                visited[ny][nx] = true; 
                q.push({ny, nx}); 
            }
        }
    }
    return false;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> h >> w;
    adj.resize(h);
    bool r = false, f = false;
    for (int i = 0; i < h; i++) {
        cin >> adj[i];
        if (!r || !f) {
           for (char c : adj[i]) {
                if (c == 'R') r = true;
                if (c == 'F') f = true;
                if (r && f) break; 
            }
        }
    }
    if ((r && !f) || (!r && f))
        cout << 1;
    else if (bfs('R') || bfs('F')) 
        cout << 2;
    else 
        cout << 3;
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70