oj.uz

답안 #474948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474948 2021-09-20T10:12:08 Z NTG Patkice II (COCI21_patkice2) C++11
110 / 110
 1328 ms 78708 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+1, oo=0x3f3f3f3f;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
#define fi first
#define sc second
#define ux(x) get<1>(x)
#define uy(x) get<2>(x)
#define w(x) get<0>(x)
int r,s,a[N][N];
char cc[7]={'o','x','.','>','<','v','^'};
int h[4]={0,0,1,-1}, c[4]={1,-1,0,0};
ii ss,ff;
bool check(int x, int n)
{
    return (x>0 && x<=n);
}
int d[N][N];
ii trace[N][N];
void dij()
{
    for(int i=0; i<=r+1; i++)
        for(int j=1; j<=s+1; j++) d[i][j]=oo, trace[i][j]={-1,-1};
    priority_queue<iii,vector<iii>,greater<iii>> q;
    q.push({0,ss.fi,ss.sc});
    d[ss.fi][ss.sc]=0;
    while(!q.empty())
    {
        int u1=ux(q.top());
        int u2=uy(q.top());
        int du=w(q.top());
        if(u1 == ff.fi && u2 == ff.sc) break;
        q.pop();
        if(du!=d[u1][u2]) continue;
        for(int i=0; i<4; i++)
            if(check(u1+h[i],r) && check(u2+c[i],s))
            {
                int v1=u1+h[i];
                int v2=u2+c[i];
                int t=1;
                if(i+3 == a[u1][u2] || (u1 == ss.fi && u2 == ss.sc)) t=0;
                if(d[v1][v2] > d[u1][u2] + t)
                {
                    d[v1][v2]=d[u1][u2]+t;
                    trace[v1][v2]={h[i],c[i]};
                    q.push({d[v1][v2],v1,v2});
                }
            }
    }
    cout<<d[ff.fi][ff.sc]<<'\n';
    ii t=ff;
    while(t!=ss)
    {
        ii tt=trace[t.fi][t.sc];
        t={t.fi-tt.fi,t.sc-tt.sc};
        for(int i=0; i<4; i++)
            if(tt.fi == h[i] && tt.sc == c[i]) {a[t.fi][t.sc]=i+3;break;}
    }
    a[ss.fi][ss.sc]=0;
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=s; j++) cout<<cc[a[i][j]];
        cout<<'\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin>>r>>s;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=s; j++)
        {
            char ch; cin>>ch;
            if(ch == 'o') a[i][j]=0, ss={i,j};
            if(ch == 'x') a[i][j]=1, ff={i,j};
            if(ch == '.') a[i][j]=2;
            if(ch == '>') a[i][j]=3;
            if(ch == '<') a[i][j]=4;
            if(ch == 'v') a[i][j]=5;
            if(ch == '^') a[i][j]=6;
        }
    dij();
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 91 ms 16440 KB Output is correct
7 Correct 114 ms 21808 KB Output is correct
8 Correct 295 ms 34500 KB Output is correct
9 Correct 573 ms 54008 KB Output is correct
10 Correct 858 ms 61348 KB Output is correct
11 Correct 1328 ms 78708 KB Output is correct