oj.uz

답안 #236155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236155 2020-05-31T10:09:29 Z topovik Portal (COCI17_portal) C++14
72 / 120
 42 ms 4352 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;

const ll oo = 1e9+7;
const ll N = 300;

pair<int,int> lf[N][N],rg[N][N],up[N][N],dn[N][N];

int kol[N][N];
bool mrk[N][N],used[N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    string a[n];
    for (int i=0; i<n; i++) cin>>a[i];

    for (int i=0; i<n; i++)
    {
        int r=1;
        for (int j=0; j<m; j++)
        {
            lf[i][j]={i,j-r};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
        r=1;
        for (int j=m-1; j>=0; j--)
        {
            rg[i][j]={i,j+r};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
    }

    for (int j=0; j<m; j++)
    {
        int r=1;
        for (int i=0; i<n; i++)
        {
            up[i][j]={i-r,j};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
        r=1;
        for (int i=n-1; i>=0; i--)
        {
            dn[i][j]={i+r,j};
            if (a[i][j]=='#') r=0;
            else              r++;
        }
    }
    queue<tuple<int,int,int> > q;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
          if (a[i][j]=='#') q.push(make_tuple(i,j,0)),mrk[i][j]=1;
    while (q.size()>0)
    {
        tuple <int,int,int> c=q.front();
        kol[get<0>(c)][get<1>(c)]=get<2>(c);
        q.pop();
        for (int i=-1; i<2; i+=2)
        {
            int sx=get<0>(c)+i;
            int sy=get<1>(c);
            if (sx>0 && sy>0 && sx<n && sy<m && !mrk[sx][sy]) q.push(make_tuple(sx,sy,get<2>(c)+1)),mrk[sx][sy]=1;
        }
        for (int i=-1; i<2; i+=2)
        {
            int sx=get<0>(c);
            int sy=get<1>(c)+i;
            if (sx>0 && sy>0 && sx<n && sy<m && !mrk[sx][sy]) q.push(make_tuple(sx,sy,get<2>(c)+1)),mrk[sx][sy]=1;
        }
    }
    multiset <tuple<int,int,int> > que;
    int sx=0,sy=0,ex=0,ey=0;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
          if (a[i][j]=='C') sx=i,sy=j;
          else
          if (a[i][j]=='F') ex=i,ey=j;
    que.insert(make_tuple(0,sx,sy));
    bool g=1;
    while (que.size()>0)
    {
        int x=get<1>(*que.begin());
        int y=get<2>(*que.begin());
        int kl=get<0>(*que.begin());
        que.erase(que.begin());
        while (used[x][y] && que.size()>0)
        {
        x=get<1>(*que.begin());
        y=get<2>(*que.begin());
        kl=get<0>(*que.begin());
        que.erase(que.begin());
        }
        if (used[x][y]) break;
        used[x][y]=1;
        if (x==ex && y==ey) {cout<<kl<<endl;g=0;break;}
        que.insert(make_tuple(kl+kol[x][y],up[x][y].f,up[x][y].s));
        que.insert(make_tuple(kl+kol[x][y],dn[x][y].f,dn[x][y].s));
        que.insert(make_tuple(kl+kol[x][y],lf[x][y].f,lf[x][y].s));
        que.insert(make_tuple(kl+kol[x][y],rg[x][y].f,rg[x][y].s));
        for (int i=-1; i<2; i+=2)
        {
            int sx=x+i;
            int sy=y;
            if (sx>0 && sy>0 && sx<n && sy<m && !used[sx][sy] && a[sx][sy]!='#') que.insert(make_tuple(kl+1,sx,sy));
        }
        for (int i=-1; i<2; i+=2)
        {
            int sx=x;
            int sy=y+i;
            if (sx>0 && sy>0 && sx<n && sy<m && !used[sx][sy] && a[sx][sy]!='#') que.insert(make_tuple(kl+1,sx,sy));
        }
    }
    if (g) cout<<"nemoguce\n";
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2688 KB Output is correct
2 Correct 7 ms 1664 KB Output is correct
3 Correct 24 ms 1664 KB Output is correct

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 2468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 4224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 4352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -