Submission #1263572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263572		denislav	Maze (JOI23_ho_t3)	C++20	100 / 100	544 ms	370272 KiB

Main

# include <iostream>
# include <vector>
# include <queue>
using namespace std;

const int MAX=6e6+11,INF=1e9;

int n,m,K;
pair<int,int> S,T;
vector<char> tab[MAX];
vector<int> dist[MAX];
int adj[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool in(int x, int y)
{
    return x>=1 and x<=n and y>=1 and y<=m;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m>>K;
    for(int i=0;i<=n+1;i++)
    {
        tab[i].resize(m+2,'.');
        dist[i].resize(m+2,INF);
    }
    cin>>S.first>>S.second;
    cin>>T.first>>T.second;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>tab[i][j];
    }

    queue<pair<int,int>> q1;
    dist[S.first][S.second]=0;
    q1.push(S);

    while(q1.size()>0)
    {
        queue<pair<pair<int,int>,pair<int,int>>> q2;
        while(q1.size()>0)
        {
            int x=q1.front().first,y=q1.front().second;
            q1.pop();
            //cout<<"->"<<x<<" "<<y<<"\n";
            for(int i=0;i<4;i++)
            {
                int x2=x+adj[i][0];
                int y2=y+adj[i][1];
                if(!in(x2,y2)) continue;
                if(tab[x2][y2]=='#')
                {
                    if(dist[x2][y2]==INF)
                    {
                        dist[x2][y2]=dist[x][y]+1;
                        q2.push({{x2,y2},{1,1}});
                    }
                }
                else
                {
                    if(dist[x2][y2]==INF)
                    {
                        dist[x2][y2]=dist[x][y];
                        q1.push({x2,y2});
                    }
                }
            }
        }

        while(q2.size()>0)
        {
            int x=q2.front().first.first,y=q2.front().first.second;
            int hor=q2.front().second.first,ver=q2.front().second.second;
            q2.pop();
            q1.push({x,y});

            for(int i=0;i<4;i++)
            {
                int x2=x+adj[i][0];
                int y2=y+adj[i][1];
                int hor2=hor+abs(adj[i][0]);
                int ver2=ver+abs(adj[i][1]);
                if(!in(x2,y2) or hor2>K or ver2>K) continue;
                if(dist[x2][y2]==INF)
                {
                    dist[x2][y2]=dist[x][y];
                    q2.push({{x2,y2},{hor2,ver2}});
                }
            }
        }
    }

    cout<<dist[T.first][T.second]<<"\n";

    return 0;
}

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