QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817091 | #1775. Deceptive Directions | ucup-team3723# | AC ✓ | 47ms | 9808kb | C++17 | 2.2kb | 2024-12-16 20:20:48 | 2024-12-16 20:20:52 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
string dir = "NESW";
int h, w;
cin >> w >> h;
vector<string> s(h);
for (int i = 0; i < h; ++i) cin >> s[i];
string t;
cin >> t;
vector<vector<int>> dis(h, vector<int> (w, 1e9));
queue<pair<int, int>> q;
for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j)
{
if (s[i][j] == 'S')
{
q.emplace(i, j);
dis[i][j] = 0;
}
}
int cnt = 0;
while (cnt < t.size())
{
int id = dir.find(t[cnt]);
++cnt;
queue<pair<int, int>> nq;
while (!q.empty())
{
auto [x, y] = q.front();
q.pop();
for (int i = 1; i < 4; ++i)
{
unsigned nx = x + dx[(i + id) % 4], ny = y + dy[(i + id) % 4];
if (nx >= h || ny >= w || s[nx][ny] == '#' || dis[nx][ny] <= dis[x][y] + 1) continue;
dis[nx][ny] = dis[x][y] + 1;
nq.emplace(nx, ny);
}
}
swap(nq, q);
}
while (!q.empty())
{
auto [x, y] = q.front();
q.pop();
s[x][y] = '!';
}
dis.assign(h, vector<int> (w, 1e9));
for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j)
{
if (s[i][j] == 'S')
{
q.emplace(i, j);
dis[i][j] = 0;
}
}
while (!q.empty())
{
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; ++i)
{
unsigned nx = x + dx[i], ny = y + dy[i];
if (nx >= h || ny >= w || s[nx][ny] == '#' || dis[nx][ny] <= dis[x][y] + 1) continue;
dis[nx][ny] = dis[x][y] + 1;
q.emplace(nx, ny);
}
}
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; ++j)
{
if (s[i][j] == '!' && dis[i][j] != t.size())
{
s[i][j] = '.';
}
}
}
for (int i = 0; i < h; ++i) cout << s[i] << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3484kb
input:
4 3 #### #S.# #### W
output:
#### #S!# ####
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 4 ### #.# #S# ### E
output:
### #!# #S# ###
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10 9 ########## #.#...#S.# ##....##.# #..##....# #........# #....###.# ##..#..#.# #...##.#.# ########## SEWSNEESE
output:
########## #.#.!.#S.# ##.!..##.# #..##....# #..!.....# #...!###.# ##..#..#.# #...##.#.# ##########
result:
ok 9 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
5 8 ##### ###.# ##..# #...# #...# ##.S# #...# ##### WSES
output:
##### ###!# ##!.# #!..# #...# ##.S# #...# #####
result:
ok 8 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
9 7 ######### #.####..# #....##.# #.......# #.......# #...#..S# ######### SENEEENN
output:
######### #.####..# #.!..##.# #!......# #.......# #!..#..S# #########
result:
ok 7 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10 8 ########## #.....#..# #..#.#...# #........# #.#......# ##......## #......S.# ########## SNWSNNSSWEE
output:
########## #!....#..# #..#.#...# #........# #.#......# ##......## #......S.# ##########
result:
ok 8 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5 8 ##### #...# #..## #.### #...# ##..# #S..# ##### WNEE
output:
##### #...# #..## #.### #..!# ##..# #S..# #####
result:
ok 8 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
50 50 ################################################## #................................................# #................................................# #................................................# #................................................# #.........................................
output:
################################################## #................................................# #................................................# #................................................# #................................................# #...............................................
result:
ok 50 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
50 50 ################################################## #................................................# #................................................# #................................................# #................................................# #.........................................
output:
################################################## #........................!.......................# #.......................!.!......................# #......................!...!.....................# #.....................!.....!....................# #....................!.......!..................
result:
ok 50 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
50 50 ################################################## #................................................# #................................................# #................................................# #................................................# #.........................................
output:
################################################## #........................!.......................# #.......................!.!......................# #......................!...!.....................# #.....................!.....!....................# #....................!.......!..................
result:
ok 50 lines
Test #11:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
50 50 ################################################## #................................................# #................................................# #................................................# #................................................# #.........................................
output:
################################################## #................................................# #................................................# #................................................# #................................................# #...............................................
result:
ok 50 lines
Test #12:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
68 36 #################################################################### #..........#...#..#..........#.....................#.##..#.........# ###.....#.##..#..#..#.....#...#................#.##.....#.#........# #.........#......#.#..#......#........#.#.#...#.#...###....#..#....# #........#......#....
output:
#################################################################### #..........#...#..#..........#.....................#.##..#.........# ###.....#.##..#..#..#.....#...#................#.##.....#.#........# #.........#......#.#..#......#........#.#.#...#.#...###....#..#....# #........#......#.#...##...
result:
ok 36 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
93 69 ############################################################################################# ##.###...#..#.##.##..###..######....##..##......#..#..#......#..##..###....#.#........####### #.#..##.#...##..###.###.###..##.##.#...#......####.###..#.##............##..#.#.###..##.#.### #.#.#...##.....
output:
############################################################################################# ##.###...#..#.##.##..###..######....##..##......#..#..#......#..##..###....#.#........####### #.#..##.#...##..###.###.###..##.##.#...#......####.###..#.##............##..#.#.###..##.#.### #.#.#...##...#.......
result:
ok 69 lines
Test #14:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
44 76 ############################################ ##.....##..###..##......#.#......#.....#.#.# ###.#.....#...#....#.....##.#.#.#....#....## ###....#..#..##..#......#.##.......#...#..## #...#.###..#...##.#....#...#..#....##....### #.##.####.....#.###.##..##...#.....###.##### #...#........#....#.##.....
output:
############################################ ##.....##..###..##......#.#......#.....#.#.# ###.#.....#...#....#.....##.#.#.#....#....## ###....#..#..##..#......#.##.......#...#..## #...#.###..#...##.#....#...#..#....##....### #.##.####.....#.###.##..##...#.....###.##### #...#........#....#.##...#.##....
result:
ok 76 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
46 65 ############################################## #.#.....#.....#.#.#.....#.#.......###........# ##.....#.#...........#.#..#....#......#.#....# ###.#.#.....#...###.###.............#.#......# #.#.#.##.....#.#.....#.#.#.##......#...##.#..# #...##..#..........#...#.......##..#...#....## #.####..#......
output:
############################################## #.#.....#.....#.#.#.....#.#.......###........# ##.....#.#...........#.#..#....#......#.#....# ###.#.#.....#...###.###.............#.#......# #.#.#.##.....#.#.....#.#.#.##......#...##.#..# #...##..#..........#...#.......##..#...#....## #.####..#....##......
result:
ok 65 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
85 45 ##################################################################################### ###.#.............#....#....#........#.......#..#..........#........................# #...#....#.............#..........#......#......##.............#..#...........#.....# #.....#.........#......................
output:
##################################################################################### ###.#.............#....#....#........#.......#..#..........#........................# #...#....#.............#..........#......#......##.............#..#...........#.....# #.....#.........#......................#.....
result:
ok 45 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
75 75 ########################################################################### #.........................................................................# #.######################################################################### #.#..................................................................
output:
########################################################################### #........................................................................!# #.######################################################################### #.#........................................................................
result:
ok 75 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
75 75 ########################################################################### #.........................................................................# #.######################################################################### #.#..................................................................
output:
########################################################################### #........................................................................!# #.######################################################################### #.#........................................................................
result:
ok 75 lines
Test #19:
score: 0
Accepted
time: 32ms
memory: 9484kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #20:
score: 0
Accepted
time: 37ms
memory: 9368kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #21:
score: 0
Accepted
time: 27ms
memory: 9476kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #22:
score: 0
Accepted
time: 25ms
memory: 9804kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #23:
score: 0
Accepted
time: 31ms
memory: 9808kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #24:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
1000 4 #####################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 4 lines
Test #25:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 1000 #### #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #.....
output:
#### #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# #..# ...
result:
ok 1000 lines
Test #26:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
1000 10 ####################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 10 lines
Test #27:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
10 1000 ########## #...#....# #..#....## #........# ###.....## #..#..#..# #........# #........# #........# #........# #.....#..# #........# #........# #........# #......#.# #.....#..# #...#....# #....#.#.# #.....#..# #....#...# #........# #....#...# #........# #.....#..# #...#....# #........# #..#.....
output:
########## #...#....# #..#....## #........# ###.....## #..#..#..# #........# #........# #........# #........# #.....#..# #........# #........# #........# #......#.# #.....#..# #...#....# #....#.#.# #.....#..# #....#...# #........# #....#...# #........# #.....#..# #...#....# #........# #..#.....# #.....
result:
ok 1000 lines
Test #28:
score: 0
Accepted
time: 47ms
memory: 9488kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #29:
score: 0
Accepted
time: 37ms
memory: 9716kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #30:
score: 0
Accepted
time: 35ms
memory: 9636kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines
Test #31:
score: 0
Accepted
time: 10ms
memory: 9480kb
input:
1000 1000 ##################################################################################################################################################################################################################################################################################################...
output:
############################################################################################################################################################################################################################################################################################################...
result:
ok 1000 lines