QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381380 | #5514. Maze | stegatxins0# | 0 | 0ms | 3812kb | C++20 | 1.8kb | 2024-04-07 17:08:34 | 2024-07-04 03:33:39 |
answer
// {{{
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
using ll = long long;
const int inf = 1073741823;
const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define rep(i, b) for (auto i = 0; i < (b); i++)
#define reps(i, b) for (auto i = 1; i <= (b); i++)
// }}}
int n,r,c;
int subtask1(vector<vector<int>> &mat, int x1, int Y1, int x2, int y2){
vector<pair<int,int>>d={{-1,0},{0,1},{1,0},{0,-1}};
queue<pair<int,int>>q;
vector<vector<int>>dp(r,vector<int>(c,INT_MAX));
dp[x1][Y1]=0;
q.push({x1,Y1});
debug(mat[x1][Y1]);
//debug(x1,Y1);
while(q.size())
{
int size=q.size();
for(int i=0;i<size;i++)
{
auto temp=q.front();
q.pop();
int x=temp.first;
int y=temp.second;
for(auto it:d)
{
int nx=x+it.first;
int ny=y+it.second;
if(nx>=0&&ny>=0&&nx<r&&ny<c&&dp[x][y]+mat[nx][ny]<dp[nx][ny])
{
dp[nx][ny]=dp[x][y]+mat[nx][ny];
q.push({nx,ny});
}
}
}
}
printf("%d",dp[x2][y2]);
exit(0);
}
int main() {
scanf("%d%d%d",&r,&c,&n);
vector<vector<int>> mat(r, vector<int>(c));
int x1, Y1, x2, y2;
cin >> x1 >> Y1 >> x2 >> y2;
//printf("%d%d",&x1,&Y1);
//printf("%d%d",&x2,&y2);
--x1, --Y1, --x2, --y2;
rep(i,r){
rep(j,c){
char inp;
scanf("%c",&inp);
if(inp=='#')mat[i][j]=1;
else mat[i][j] = 0;
}
}
//debug(mat);
if(n==1){subtask1(mat,x1,Y1,x2,y2);}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
31 32 1 25 22 5 3 ################################ ################################ .############################### .############################### ##..###############.############ ###.###############.############ #####.########################## ###.#.########################## ###.##############...
output:
21
result:
wrong answer 1st lines differ - expected: '26', found: '21'
Subtask #2:
score: 0
Wrong Answer
Test #52:
score: 0
Wrong Answer
time: 0ms
memory: 3664kb
input:
3 6 2 2 1 3 3 ...### ..##.. #..###
output:
result:
wrong answer 1st lines differ - expected: '0', found: ''
Subtask #3:
score: 0
Wrong Answer
Test #64:
score: 0
Wrong Answer
time: 0ms
memory: 3676kb
input:
35 60 20 3 60 2 44 .#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####. #.#......#.####..####...#...#......#........####....##.#.### .#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##. .#.#...##..#.##.......#......##......####...##.##..##.#....# #...#.......#..#..#...#.#####.##.###....
output:
result:
wrong answer 1st lines differ - expected: '1', found: ''
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%