Submission #1023301

#TimeUsernameProblemLanguageResultExecution timeMemory
1023301snpmrnhlolMaze (JOI23_ho_t3)C++17
94 / 100
1616 ms1143464 KiB
#include<bits/stdc++.h> using namespace std; const int N = 6e6; const int inf = 2e9; int k,n,m,sx,sy,ex,ey; int d[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int ans = inf; cin>>n>>m>>k; cin>>sx>>sy>>ex>>ey; vector<vector <char>> v(n + 2,vector<char>(m + 2,0)); vector<vector <vector<bool>>> vis(n + 2,vector<vector<bool>>(m + 2,vector<bool>(2,0))); vector <array<int,2>> q; vector <array<int,3>> q2; for(int i = 0;i < n + 2;i++){ v[i][0] = 2; v[i][m + 1] = 2; } for(int i = 0;i < m + 2;i++){ v[0][i] = 2; v[n + 1][i] = 2; } for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ char ch; cin>>ch; if(ch == '.'){ v[i + 1][j + 1] = 0; }else{ v[i + 1][j + 1] = 1; } } } vis[sx][sy][0] = 1; int g = 0; q.push_back({sx,sy}); for(int i = 0;i <= n + m;i++){ int pt = 0; q2.clear(); while(pt < q.size()){ auto x = q[pt];pt++;g++; if(x[0] == ex && x[1] == ey){ ans = i; } ///bfs if(!vis[x[0]][x[1]][1]){ q2.push_back({x[0],x[1],0}); } for(int j = 0;j < 4;j++){ int nx = x[0] + d[j][0]; int ny = x[1] + d[j][1]; if(!vis[nx][ny][0] && v[nx][ny] == 0){ vis[nx][ny][0] = 1; q.push_back({nx,ny}); } } } q.clear(); pt = 0; while(pt < q2.size()){ auto x = q2[pt];pt++;g++; if(!vis[x[0]][x[1]][0]){ q.push_back({x[0],x[1]}); vis[x[0]][x[1]][0] = 1; } if(x[2] != k - 1){ for(int j = 0;j < 8;j++){ int nx = x[0] + d[j][0]; int ny = x[1] + d[j][1]; if(!vis[nx][ny][1] && v[nx][ny] != 2){ vis[nx][ny][1] = 1; q2.push_back({nx,ny,x[2] + 1}); } } }else{ for(int j = 0;j < 4;j++){ int nx = x[0] + d[j][0]; int ny = x[1] + d[j][1]; if(!vis[nx][ny][0] && v[nx][ny] != 2){ vis[nx][ny][0] = 1; q.push_back({nx,ny}); } } } } } assert(g <= 2*N); cout<<ans<<'\n'; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(pt < q.size()){
      |               ~~~^~~~~~~~~~
Main.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         while(pt < q2.size()){
      |               ~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...