Submission #1066233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066233		Dennis_Jason	Maze (JOI23_ho_t3)	C++14	100 / 100	491 ms	123744 KiB

Main

#include <bits/stdc++.h>
#define NMAX 1010
//#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF  1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ----------------DEMONSTRATION-------------------
            1 2 2 3 4 2

                    1 2 3 4 5 6
            1 2 3              4 5 6
        1 2       3         4 5       6
    1       2             4     5
    ---------------------END------------------------
 */
int r,c,n;
int i_s,j_s,i_f,j_f;
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};
bool inmat(int i,int j)
{
    return i>=1 && i<=r && j>=1 && j<=c;
}
signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>r>>c>>n;
    cin>>i_s>>j_s;
    cin>>i_f>>j_f;
    vector<vector<int>>mat(r+1,vector<int>(c+1));
    vector<vector<int>>dist(r+1,vector<int>(c+1,-1));
    queue<tpl>white,black;
    for(int i=1;i<=r;++i)
    {
        for(int j=1;j<=c;++j)
        {
            char x;
            cin>>x;
            if(x=='.')
            {
                mat[i][j]=0;
            }
            else
            {
                mat[i][j]=1;
            }
        }
    }
    dist[i_s][j_s]=0;
    white.push({i_s,j_s,0,0});
    while(!white.empty() || !black.empty())
    {
        while(!black.empty())
        {
            auto [i,j,x,y]=black.front();
            black.pop();
//            cout<<i<<" "<<j<<"b"<<nl;
            if(x==0 || y==0)
            {
                white.push({i,j,0,0});
            }
            for(int d=0;d<4;++d)
            {
                int inou=i+di[d];
                int jnou=j+dj[d];
                int pas_x=x-abs(di[d]);
                int pas_y=y-abs(dj[d]);
                if((pas_x>=0 && pas_y>=0)&& inmat(inou,jnou) && dist[inou][jnou]==-1)
                {
                    dist[inou][jnou]=dist[i][j];
                    black.push({inou,jnou,pas_x,pas_y});
                }

            }
        }

        while(!white.empty())
        {
            auto [i,j,x,y]=white.front();
            white.pop();
//            cout<<i<<" "<<j<<"w"<<nl;
            for(int d=0;d<4;++d)
            {
                int inou=i+di[d];
                int jnou=j+dj[d];
                if(inmat(inou,jnou) && dist[inou][jnou]==-1)
                {
                    if(mat[inou][jnou]==1)
                    {
                        dist[inou][jnou]=dist[i][j]+1;
                        black.push({inou,jnou,n-1,n-1});
                    }
                    else
                    {
                        dist[inou][jnou]=dist[i][j];
                        white.push({inou,jnou,0,0});
                    }
                }
            }
        }
    }
    cout<<dist[i_f][j_f];

    return 0;
}

Compilation message (stderr)

Main.cpp:9: warning: "LLONG_MAX" redefined
    9 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from Main.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      | 
Main.cpp: In function 'int main()':
Main.cpp:69:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |             auto [i,j,x,y]=black.front();
      |                  ^
Main.cpp:93:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |             auto [i,j,x,y]=white.front();
      |                  ^

• 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