Submission #1018941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018941		andrei_iorgulescu	Maze (JOI23_ho_t3)	C++14	8 / 100	163 ms	14416 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int inf = 1e9;
vector<int> dl;
vector<int> dc;

int r,c,n;
int xs,ys,xf,yf;
vector<vector<char>> a;
vector<vector<int>> d;
vector<vector<bool>> viz;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> r >> c >> n >> xs >> ys >> xf >> yf;
    a.resize(r + 1);
    for (int i = 1; i <= r; i++)
    {
        a[i].resize(c + 1);
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];
    }
    d.resize(r + 1);
    for (int i = 1; i <= r; i++)
        d[i].resize(c + 1);
    viz.resize(r + 1);
    for (int i = 1; i <= r; i++)
        viz[i].resize(c + 1);
    deque<pair<int,int>> dq;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            d[i][j] = inf;
    d[xs][ys] = 0;
    dq.push_back({xs,ys});
    dl = {-1,0,1,0,-n,-n,-(n - 1),(n - 1),n,n,(n - 1),-(n - 1)};
    dc = {0,1,0,-1,-(n - 1),(n - 1),n,n,(n - 1),-(n - 1),-n,-n};
    while (!dq.empty())
    {
        pair<int,int> nod = dq.front();
        dq.pop_front();
        if (viz[nod.first][nod.second])
            break;
        viz[nod.first][nod.second] = true;
        if (abs(nod.first - xf) <= n and abs(nod.second - yf) <= n and abs(nod.first - xf) + abs(nod.second - yf) != 2 * n)
        {
            if (d[xf][yf] > 1 + d[nod.first][nod.second])
            {
                d[xf][yf] = 1 + d[nod.first][nod.second];
                dq.push_back({xf,yf});
            }
        }
        for (int i = 0; i < dl.size(); i++)
        {
            int nx = nod.first + dl[i],ny = nod.second + dc[i];
            nx = max(nx,1);
            nx = min(nx,r);
            ny = max(ny,1);
            ny = min(ny,c);
            if (i >= 4 or a[nx][ny] == '#')
            {
                if (d[nx][ny] > 1 + d[nod.first][nod.second])
                {
                    d[nx][ny] = 1 + d[nod.first][nod.second];
                    dq.push_back({nx,ny});
                }
            }
            else
            {
                if (d[nx][ny] > d[nod.first][nod.second])
                {
                    d[nx][ny] = d[nod.first][nod.second];
                    dq.push_front({nx,ny});
                }
            }
        }
    }
    cout << d[xf][yf];
    return 0;
}

///nu m-as fi gandit acum cateva luni ca doar colturile sunt relevante (man ce bot eram)

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < dl.size(); i++)
      |                         ~~^~~~~~~~~~~

• Subtask 1: 8 / 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