Submission #1155213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155213		Marco_Escandon	Maze (JOI23_ho_t3)	C++20	0 / 100	0 ms	328 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
ll dx[]={1,0,-1,0};
ll dy[]={0,-1,0,1};
vector<string> cad;
vector<vector<ll>> d;
bool inside(pair<ll,ll> a, pair<ll,ll> b, pair<ll,ll> c) { return (a.x<=c.x&&b.x>=c.x&&a.y<=c.y&&b.y>=c.y); }
int main()
{
    ll n,m,k;
    pair<ll,ll> inicio,fin;
    cin>>n>>m>>k>>inicio.x>>inicio.y>>fin.x>>fin.y;
    inicio.x--;
    inicio.y--;
    fin.x--;
    fin.y--;
    cad.resize(n);d.assign(n,vector<ll>(m,1e9));
    for(int i=0; i<n; i++)
        cin>>cad[i];
    deque<pair<ll,ll>> q;
    q.push_front(inicio);
    d[inicio.x][inicio.y]=0;
    while(!q.empty())
    {
        pair<ll,ll> temp1=q.front();q.pop_front();
        for(int i=0; i<4; i++)
        {
            pair<ll,ll> temp=temp1;
            temp.x+=dx[i];temp.y+=dy[i];
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]<d[temp.x][temp.y]&&cad[temp.x][temp.y]=='.')
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y];
                q.push_front(temp);
            }
        }
        for(int i=0; i<=k; i++)
        {
            for(int j=0; j<=k; j++)
            {
                if(i+j>=2*k) continue;
                pair<ll,ll> temp=temp1;
                temp.x+=i;temp.y+=j;
                if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
                    d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                temp=temp1;
                temp.x+=i;temp.y-=j;
                if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
                    d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                temp=temp1;
                temp.x-=i;temp.y+=j;
                if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
                    d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                temp=temp1;
                temp.x-=i;temp.y-=j;
                if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
                    d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
            }
        }
        for(int i=0; i<k; i++)
        {
            pair<ll,ll> temp=temp1;
            temp.x+=i;temp.y+=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.x+=i;temp.y-=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.x-=i;temp.y+=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.x-=i;temp.y-=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.y-=i;temp.x+=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.y-=i;temp.x-=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.y+=i;temp.x+=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
            temp=temp1;
            temp.y+=i;temp.x-=k;
            if(inside({0,0},{n-1,m-1},temp)&&d[temp1.x][temp1.y]+1<d[temp.x][temp.y])
            {
                d[temp.x][temp.y]=d[temp1.x][temp1.y]+1;
                q.push_back(temp);
            }
        }
    }
    cout<<d[fin.x][fin.y];
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6