| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1105427 |
2024-10-26T10:51:21 Z |
vjudge1 |
Maze (JOI23_ho_t3) |
C++17 |
|
1 ms |
336 KB |
#include <bits/stdc++.h>
#define _files
#define _multitest
#define _Debug_
using namespace std;
void just_do_it();
int main() {
#define task ""
#ifdef _files_
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
#endif
#ifdef _Debug
ios_base::sync_with_stdio(0);
#endif
cin.tie(0);
just_do_it();
return 0;
}
#define __builtin_popcount __builtin_popcountll
#define BIT(x, i) (((x)>> (i))& (1LL))
#define MASK(x) (1LL<< (x))
#define MOD 1000000007
#define ll long long
const int maxm= (int)1e6, maxn= (int)1e5, maxb= (int)1e3;
ll INF= (ll)1e18;
const int dx[]= {-1, 1, 0, 0};
const int dy[]= { 0, 0, -1, 1};
struct DSU{
DSU(){}
vector<int> f;
void init(int n){
f.resize(n+ 1);
iota(f.begin(), f.end(), 0);
}
int lab(int u){
while(u!= f[u]){
u= f[u]= f[f[u]];
}
return u;
}
void mer(int u, int v){
u= lab(u);
v= lab(v);
if(u!= v){
f[v]= u;
}
}
};
struct state{
state(){}
int t, x, y;
state(int _t, int _x, int _y){
t= _t;
x= _x;
y= _y;
}
};
vector<vector<char> > a;
vector<vector<bool> > vis;
vector<DSU> nxtr, nxtc;
pair<int, int> sta, en;
int r, c, n;
deque<state> st;
bool ok(int pr, int pc){
return ((0< pr)&& (pr<= r)&& (0< pc)&& (pc<= c)&& (a[pr][pc]== '.'));
}
void input(){
cin>> r>> c>> n>> sta.first>> sta.second>> en.first>> en.second;
a.resize(r+ 3, vector<char> (c+ 3));
vis.resize(r+ 3, vector<bool> (c+ 3));
nxtr.resize(c+ 3);
for(int i= 1; i<= c; i++){
nxtr[i].init(r+ 3);
}
nxtc.resize(r+ 2);
for(int i= 1; i<= r; i++){
nxtc[i].init(c+ 3);
}
for(int i= 1; i<= r; i++){
for(int j= 1; j<= c; j++){
cin>> a[i][j];
}
}
}
void prepare(){
}
void solve(){
st.push_back(state(0, sta.first, sta.second));
while(st.size()){
int t= st.front().t, pr= st.front().x, pc= st.front().y;st.pop_front();
if(vis[pr][pc]) continue;
else vis[pr][pc]= true;
if((pr== en.first)&& (pc== en.second)){
cout<< t;
return;
}
for(int k= 0; k< 4; k++){
int nr= pr+ dx[k], nc= pc+ dy[k];
if(ok(nr, nc)&& (vis[nr][nc]== false)){
st.push_front(state(t, nr, nc));
}
}
int mnr= max(pr- n, 1), mxr= min(pr+ n, r), mnc= max(pc- n, 1), mxc= min(pc+ n, c);
for(int i= nxtr[mnc].lab(mnr); i<= mxr; i= nxtr[mnc].lab(i+ 1)){
for(int j= nxtc[i].lab(mnc); j<= mxc; j= nxtc[i].lab(j+ 1)){
st.push_back(state(t+ 1, i, j));
nxtc[i].mer(j+ 1, j);
}
nxtr[mnc].mer(i+ 1, i);
}
}
}
void printans(){
}
void reset(){
}
void test(){
input();
prepare();
solve();
printans();
reset();
}
void just_do_it() {
int nTest= 1;
#ifdef _multitest_
cin>>nTest;
#endif
for (int it= 1; it <= nTest; it++) {
test();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
