oj.uz

답안 #742292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
742292 2023-05-16T04:29:41 Z irmuun Tracks in the Snow (BOI13_tracks) C++17
51.875 / 100
 483 ms 1048576 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int h,w;
    cin>>h>>w;
    string s[h+5];
    int used[h+5][w+5];
    for(int i=0;i<h;i++){
        cin>>s[i];
        for(int j=0;j<w;j++){
            used[i][j]=0;
        }
    }
    used[0][0]=1;
    deque<pair<int,int>>q[h*w+5];
    q[1].pb({0,0});
    for(int i=1;i<=h*w+1;i++){
        if(q[i].size()==0){
            cout<<i-1;
            return 0;
        }
        while(!q[i].empty()){
            int x=q[i].front().ff,y=q[i].front().ss;
            q[i].pop_front();
            if(x>0&&used[x-1][y]==0){
                used[x-1][y]=1;
                if(s[x-1][y]==s[x][y]){
                    q[i].pb({x-1,y});
                }
                else if(s[x-1][y]!='.'){
                    q[i+1].pb({x-1,y});
                }
            }
            if(x<h-1&&used[x+1][y]==0){
                used[x+1][y]=1;
                if(s[x+1][y]==s[x][y]){
                    q[i].pb({x+1,y});
                }
                else if(s[x+1][y]!='.'){
                    q[i+1].pb({x+1,y});
                }
            }
            if(y>0&&used[x][y-1]==0){
                used[x][y-1]=1;
                if(s[x][y-1]==s[x][y]){
                    q[i].pb({x,y-1});
                }
                else if(s[x][y-1]!='.'){
                    q[i+1].pb({x,y-1});
                }
            }
            if(y<w-1&&used[x][y+1]==0){
                used[x][y+1]=1;
                if(s[x][y+1]==s[x][y]){
                    q[i].pb({x,y+1});
                }
                else if(s[x][y+1]!='.'){
                    q[i+1].pb({x,y+1});
                }
            }
        }
    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 163784 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 2004 KB Output is correct
4 Correct 69 ms 104464 KB Output is correct
5 Correct 38 ms 56932 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 2004 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 5 ms 6996 KB Output is correct
10 Correct 30 ms 44372 KB Output is correct
11 Correct 20 ms 27432 KB Output is correct
12 Correct 42 ms 59080 KB Output is correct
13 Correct 36 ms 56876 KB Output is correct
14 Correct 35 ms 56836 KB Output is correct
15 Correct 105 ms 169824 KB Output is correct
16 Correct 109 ms 163772 KB Output is correct
17 Correct 103 ms 161836 KB Output is correct
18 Correct 70 ms 104500 KB Output is correct

Subtask #2
21.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 34004 KB Output is correct
2 Runtime error 445 ms 1048576 KB Execution killed with signal 9
3 Runtime error 403 ms 1048576 KB Execution killed with signal 9
4 Runtime error 444 ms 1048576 KB Execution killed with signal 9
5 Runtime error 414 ms 1048576 KB Execution killed with signal 9
6 Runtime error 430 ms 1048576 KB Execution killed with signal 9
7 Correct 21 ms 30272 KB Output is correct
8 Correct 23 ms 34064 KB Output is correct
9 Correct 30 ms 40064 KB Output is correct
10 Correct 14 ms 22096 KB Output is correct
11 Correct 22 ms 32340 KB Output is correct
12 Correct 9 ms 15544 KB Output is correct
13 Runtime error 443 ms 1048576 KB Execution killed with signal 9
14 Correct 428 ms 611312 KB Output is correct
15 Correct 483 ms 677152 KB Output is correct
16 Correct 325 ms 434432 KB Output is correct
17 Runtime error 409 ms 1048576 KB Execution killed with signal 9
18 Runtime error 407 ms 1048576 KB Execution killed with signal 9
19 Runtime error 424 ms 1048576 KB Execution killed with signal 9
20 Runtime error 411 ms 1048576 KB Execution killed with signal 9
21 Runtime error 394 ms 1048576 KB Execution killed with signal 9
22 Runtime error 409 ms 1048576 KB Execution killed with signal 9
23 Runtime error 434 ms 1048576 KB Execution killed with signal 9
24 Runtime error 400 ms 1048576 KB Execution killed with signal 9
25 Runtime error 399 ms 1048576 KB Execution killed with signal 9
26 Runtime error 398 ms 1048576 KB Execution killed with signal 9
27 Runtime error 393 ms 1048576 KB Execution killed with signal 9
28 Runtime error 385 ms 1048576 KB Execution killed with signal 9
29 Runtime error 392 ms 1048576 KB Execution killed with signal 9
30 Runtime error 385 ms 1048576 KB Execution killed with signal 9
31 Runtime error 395 ms 1048576 KB Execution killed with signal 9
32 Runtime error 391 ms 1048576 KB Execution killed with signal 9