제출 #236156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236156		topovik	Portal (COCI17_portal)	C++14	120 / 120	240 ms	11640 KiB

portal

#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 = 500;

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12