Submission #932807

#	Time	Username	Problem	Language	Result	Execution time	Memory
932807		Yazan_Alattar	Maze (JOI23_ho_t3)	C++14	100 / 100	1291 ms	855148 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 6000007;
const ll inf = 1e9;
const ll INF = 1e12;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};

string s[M];
vector <int> visit[M];
int n, m, block, startX, startY, endX, endY;

bool Valid(int x, int y){
    if(visit[x][y] || x <= 0 || y <= 0 || x > n || y > m) return 0;
    return 1;
}

int bfs(){
    queue < pair < pair <int,int>, pair <int, int> > > zeroEdge, oneEdge;

    zeroEdge.push({{startX, startY}, {0, 0}});

    while(!zeroEdge.empty() || !oneEdge.empty()){
        if(zeroEdge.empty())
            swap(zeroEdge, oneEdge);

        int x = zeroEdge.front().F.F;
        int y = zeroEdge.front().F.S;
        int remainingMoves = zeroEdge.front().S.F;
        int dist = zeroEdge.front().S.S;
        zeroEdge.pop();

        if(x == endX && y == endY) return dist;
        if(!Valid(x, y)) continue;

        visit[x][y] = 1;


        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(s[nx][ny] == '.') zeroEdge.push({{nx, ny}, {max(0, remainingMoves - 1), dist}});
        }

        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(remainingMoves > 0) zeroEdge.push({{nx, ny}, {remainingMoves - 1, dist}});
            else oneEdge.push({{nx, ny}, {block - 1, dist + 1}});
        }

        for(int i = 4; i < 8; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(remainingMoves > 1) zeroEdge.push({{nx, ny}, {remainingMoves - 1, dist}});
            else if(block > 1) oneEdge.push({{nx, ny}, {block - 1, dist + 1}});
        }
    }
}

void solve(int _){
    cin >> n >> m >> block;
    cin >> startX >> startY >> endX >> endY;

    for(int i = 1; i <= n; ++i){
        cin >> s[i];
        s[i] = '#' + s[i];
        visit[i].resize(m + 2);
    }
    visit[0] .resize(m + 2);
    visit[n + 1] .resize(m + 2);

    cout << bfs() << endl;
    return;
}

int main(){
//    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; ++i) solve(t);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int bfs()':
Main.cpp:28:56: warning: control reaches end of non-void function [-Wreturn-type]
   28 |     queue < pair < pair <int,int>, pair <int, int> > > zeroEdge, oneEdge;
      |                                                        ^~~~~~~~

• 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