Task: | Chess board tour |
Sender: | ZDHKLV |
Submission time: | 2024-11-04 17:14:40 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | TIME LIMIT EXCEEDED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | ACCEPTED | 0.00 s | details |
#19 | ACCEPTED | 0.00 s | details |
#20 | ACCEPTED | 0.00 s | details |
#21 | ACCEPTED | 0.01 s | details |
#22 | ACCEPTED | 0.00 s | details |
#23 | ACCEPTED | 0.01 s | details |
#24 | ACCEPTED | 0.00 s | details |
#25 | ACCEPTED | 0.00 s | details |
#26 | ACCEPTED | 0.00 s | details |
#27 | TIME LIMIT EXCEEDED | -- | details |
#28 | TIME LIMIT EXCEEDED | -- | details |
#29 | TIME LIMIT EXCEEDED | -- | details |
#30 | TIME LIMIT EXCEEDED | -- | details |
#31 | TIME LIMIT EXCEEDED | -- | details |
#32 | ACCEPTED | 0.18 s | details |
#33 | TIME LIMIT EXCEEDED | -- | details |
#34 | TIME LIMIT EXCEEDED | -- | details |
#35 | ACCEPTED | 0.01 s | details |
#36 | ACCEPTED | 0.00 s | details |
#37 | TIME LIMIT EXCEEDED | -- | details |
#38 | TIME LIMIT EXCEEDED | -- | details |
#39 | TIME LIMIT EXCEEDED | -- | details |
#40 | TIME LIMIT EXCEEDED | -- | details |
#41 | TIME LIMIT EXCEEDED | -- | details |
#42 | TIME LIMIT EXCEEDED | -- | details |
#43 | TIME LIMIT EXCEEDED | -- | details |
#44 | TIME LIMIT EXCEEDED | -- | details |
#45 | ACCEPTED | 0.01 s | details |
#46 | ACCEPTED | 0.12 s | details |
#47 | TIME LIMIT EXCEEDED | -- | details |
#48 | TIME LIMIT EXCEEDED | -- | details |
#49 | TIME LIMIT EXCEEDED | -- | details |
#50 | TIME LIMIT EXCEEDED | -- | details |
#51 | TIME LIMIT EXCEEDED | -- | details |
#52 | TIME LIMIT EXCEEDED | -- | details |
#53 | TIME LIMIT EXCEEDED | -- | details |
#54 | TIME LIMIT EXCEEDED | -- | details |
#55 | TIME LIMIT EXCEEDED | -- | details |
#56 | TIME LIMIT EXCEEDED | -- | details |
Code
#include <bits/stdc++.h> using namespace std; bool dfs(int x, int y, int seen, vector<vector<bool>> &visited, int n, int m, vector<char> &output) { if (visited[x][y]) { if (x == 0 && y == 0) { if (seen < n * m) return false; return true; } return false; } bool block_up = (y == 0 || visited[x][y-1]); bool block_left = (x == 0 || visited[x-1][y]); bool block_right = (x == n-1 || visited[x+1][y]); bool block_down = (y == m-1 || visited[x][y+1]); bool can_go_left = (x > 0 && !visited[x-1][y]); bool can_go_right = (x+1 < n && !visited[x+1][y]); bool can_go_up = (y > 0 && !visited[x][y-1]); bool can_go_down = (y+1 < m && !visited[x][y+1]); if (block_up && (can_go_left && can_go_right)) return false; if (block_down && (can_go_left && can_go_right)) return false; if (block_left && (can_go_up && can_go_down)) return false; if (block_right && (can_go_up && can_go_down)) return false; visited[x][y] = true; if (x > 0 && (!visited[x-1][y] || (x-1 == 0 && y == 0))) { output.push_back('U'); bool b = dfs(x-1, y, seen+1, visited, n, m, output); if (b) return true; output.pop_back(); } if (x+1 < n && !visited[x+1][y]) { output.push_back('D'); bool b = dfs(x+1, y, seen+1, visited, n, m, output); if (b) return true; output.pop_back(); } if (y > 0 && (!visited[x][y-1] || (x == 0 && y-1 == 0))) { output.push_back('L'); bool b = dfs(x, y-1, seen+1, visited, n, m, output); if (b) return true; output.pop_back(); } if (y+1 < m && !visited[x][y+1]) { output.push_back('R'); bool b = dfs(x, y+1, seen+1, visited, n, m, output); if (b) return true; output.pop_back(); } visited[x][y] = false; return false; } /* void dfs(int x, int y, int n, int m) { vector<vector<bool>> visited(n, vector<bool>(m, false)); typedef struct { int x, y, seen; } state_t; stack<state_t> s; s.push({ x, y, 0 }); vector<char> events; while (!s.empty()) { state_t pos = s.top(); s.pop(); if (visited[pos.x][pos.y]) { if (pos.x == 0 && pos.y == 0) { // if (pos.seen < n * m) continue; else { bool found = false; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!visited[i][j]) { found = true; break; } } if (found) break; } if (found) continue; cout << "ok" << endl; } } continue; } visited[pos.x][pos.y] = true; if (pos.x > 0 && !visited[pos.x-1][pos.y]) { events.push_back('L'); s.push({ pos.x-1, pos.y, pos.seen+1 }); } if (pos.x+1 < n && !visited[pos.x+1][pos.y]) { events.push_back('D'); s.push({ pos.x+1, pos.y, pos.seen+1 }); } if (pos.y > 0 && !visited[pos.x][pos.y-1]) { events.push_back('U'); s.push({ pos.x, pos.y-1, pos.seen+1 }); } if (pos.y+1 < m && !visited[pos.x][pos.y+1]) { events.push_back('D'); s.push({ pos.x, pos.y+1, pos.seen+1 }); } } } */ int main() { int n, m; cin >> n >> m; vector<vector<bool>> visited(n, vector<bool>(m, false)); vector<char> output; bool b = dfs(0, 0, 0, visited, n, m, output); if (!b) { cout << -1 << endl; } else { for (char c : output) cout << c; cout << endl; } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
2 2 |
correct output |
---|
DRUL |
user output |
---|
DRUL |
Test 2
Verdict: ACCEPTED
input |
---|
2 2 |
correct output |
---|
DRUL |
user output |
---|
DRUL |
Test 3
Verdict: ACCEPTED
input |
---|
2 3 |
correct output |
---|
RRDLLU |
user output |
---|
DRRULL |
Test 4
Verdict: ACCEPTED
input |
---|
2 2 |
correct output |
---|
DRUL |
user output |
---|
DRUL |
Test 5
Verdict: ACCEPTED
input |
---|
4 4 |
correct output |
---|
DDDRUURDDRUUULLL |
user output |
---|
DDDRRRUUULDDLUUL |
Test 6
Verdict: ACCEPTED
input |
---|
3 3 |
correct output |
---|
-1 |
user output |
---|
-1 |
Test 7
Verdict: ACCEPTED
input |
---|
4 4 |
correct output |
---|
DDDRUURDDRUUULLL |
user output |
---|
DDDRRRUUULDDLUUL |
Test 8
Verdict: ACCEPTED
input |
---|
3 5 |
correct output |
---|
-1 |
user output |
---|
-1 |
Test 9
Verdict: ACCEPTED
input |
---|
3 2 |
correct output |
---|
DDRUUL |
user output |
---|
DDRUUL |
Test 10
Verdict: ACCEPTED
input |
---|
4 2 |
correct output |
---|
DDDRUUUL |
user output |
---|
DDDRUUUL |
Test 11
Verdict: ACCEPTED
input |
---|
5 5 |
correct output |
---|
-1 |
user output |
---|
-1 |
Test 12
Verdict: ACCEPTED
input |
---|
2 2 |
correct output |
---|
DRUL |
user output |
---|
DRUL |
Test 13
Verdict: ACCEPTED
input |
---|
5 5 |
correct output |
---|
-1 |
user output |
---|
-1 |
Test 14
Verdict: ACCEPTED
input |
---|
2 2 |
correct output |
---|
DRUL |
user output |
---|
DRUL |
Test 15
Verdict: ACCEPTED
input |
---|
5 2 |
correct output |
---|
DDDDRUUUUL |
user output |
---|
DDDDRUUUUL |
Test 16
Verdict: ACCEPTED
input |
---|
2 3 |
correct output |
---|
RRDLLU |
user output |
---|
DRRULL |
Test 17
Verdict: ACCEPTED
input |
---|
6 7 |
correct output |
---|
RRRRRRDLLLLLDRRRRRDLLLLLDRRRRR... |
user output |
---|
DDDDDRRRRRRUUUUULDDDDLUUUULDDD... |
Test 18
Verdict: ACCEPTED
input |
---|
5 10 |
correct output |
---|
DDDDRUUURDDDRUUURDDDRUUURDDDRU... |
user output |
---|
DDDDRRRRRRRRRUUUULDDDLUUULDDDL... |
Test 19
Verdict: ACCEPTED
input |
---|
5 3 |
correct output |
---|
-1 |
user output |
---|
-1 |
Test 20
Verdict: ACCEPTED
input |
---|
6 2 |
correct output |
---|
DDDDDRUUUUUL |
user output |
---|
DDDDDRUUUUUL |
Test 21
Verdict: ACCEPTED
input |
---|
10 10 |
correct output |
---|
DDDDDDDDDRUUUUUUUURDDDDDDDDRUU... |
user output |
---|
DDDDDDDDDRRRRRRRRRUUUUUUUUULDD... Truncated |
Test 22
Verdict: ACCEPTED
input |
---|
3 2 |
correct output |
---|
DDRUUL |
user output |
---|
DDRUUL |
Test 23
Verdict: ACCEPTED
input |
---|
10 10 |
correct output |
---|
DDDDDDDDDRUUUUUUUURDDDDDDDDRUU... |
user output |
---|
DDDDDDDDDRRRRRRRRRUUUUUUUUULDD... Truncated |
Test 24
Verdict: ACCEPTED
input |
---|
2 4 |
correct output |
---|
DRRRULLL |
user output |
---|
DRRRULLL |
Test 25
Verdict: ACCEPTED
input |
---|
9 2 |
correct output |
---|
DDDDDDDDRUUUUUUUUL |
user output |
---|
DDDDDDDDRUUUUUUUUL |
Test 26
Verdict: ACCEPTED
input |
---|
2 5 |
correct output |
---|
RRRRDLLLLU |
user output |
---|
DRRRRULLLL |
Test 27
Verdict: TIME LIMIT EXCEEDED
input |
---|
56 60 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 28
Verdict: TIME LIMIT EXCEEDED
input |
---|
43 100 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 29
Verdict: TIME LIMIT EXCEEDED
input |
---|
45 20 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 30
Verdict: TIME LIMIT EXCEEDED
input |
---|
56 9 |
correct output |
---|
RRRRRRRRDLLLLLLLDRRRRRRRDLLLLL... |
user output |
---|
(empty) |
Test 31
Verdict: TIME LIMIT EXCEEDED
input |
---|
97 91 |
correct output |
---|
-1 |
user output |
---|
(empty) |
Test 32
Verdict: ACCEPTED
input |
---|
23 7 |
correct output |
---|
-1 |
user output |
---|
-1 |
Test 33
Verdict: TIME LIMIT EXCEEDED
input |
---|
90 95 |
correct output |
---|
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR... |
user output |
---|
(empty) |
Test 34
Verdict: TIME LIMIT EXCEEDED
input |
---|
9 24 |
correct output |
---|
DDDDDDDDRUUUUUUURDDDDDDDRUUUUU... |
user output |
---|
(empty) |
Test 35
Verdict: ACCEPTED
input |
---|
88 3 |
correct output |
---|
RRDLDRDLDRDLDRDLDRDLDRDLDRDLDR... |
user output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... Truncated |
Test 36
Verdict: ACCEPTED
input |
---|
3 38 |
correct output |
---|
DDRURDRURDRURDRURDRURDRURDRURD... |
user output |
---|
DDRRRRRRRRRRRRRRRRRRRRRRRRRRRR... Truncated |
Test 37
Verdict: TIME LIMIT EXCEEDED
input |
---|
111 119 |
correct output |
---|
-1 |
user output |
---|
(empty) |
Test 38
Verdict: TIME LIMIT EXCEEDED
input |
---|
84 200 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 39
Verdict: TIME LIMIT EXCEEDED
input |
---|
88 38 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 40
Verdict: TIME LIMIT EXCEEDED
input |
---|
111 16 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 41
Verdict: TIME LIMIT EXCEEDED
input |
---|
194 181 |
correct output |
---|
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR... |
user output |
---|
(empty) |
Test 42
Verdict: TIME LIMIT EXCEEDED
input |
---|
46 12 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 43
Verdict: TIME LIMIT EXCEEDED
input |
---|
179 190 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 44
Verdict: TIME LIMIT EXCEEDED
input |
---|
17 47 |
correct output |
---|
-1 |
user output |
---|
(empty) |
Test 45
Verdict: ACCEPTED
input |
---|
175 4 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... Truncated |
Test 46
Verdict: ACCEPTED
input |
---|
4 74 |
correct output |
---|
DDDRUURDDRUURDDRUURDDRUURDDRUU... |
user output |
---|
DDDRRRRRRRRRRRRRRRRRRRRRRRRRRR... Truncated |
Test 47
Verdict: TIME LIMIT EXCEEDED
input |
---|
550 594 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 48
Verdict: TIME LIMIT EXCEEDED
input |
---|
418 998 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 49
Verdict: TIME LIMIT EXCEEDED
input |
---|
437 186 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 50
Verdict: TIME LIMIT EXCEEDED
input |
---|
552 72 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 51
Verdict: TIME LIMIT EXCEEDED
input |
---|
968 901 |
correct output |
---|
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR... |
user output |
---|
(empty) |
Test 52
Verdict: TIME LIMIT EXCEEDED
input |
---|
223 57 |
correct output |
---|
-1 |
user output |
---|
(empty) |
Test 53
Verdict: TIME LIMIT EXCEEDED
input |
---|
893 948 |
correct output |
---|
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD... |
user output |
---|
(empty) |
Test 54
Verdict: TIME LIMIT EXCEEDED
input |
---|
78 229 |
correct output |
---|
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR... |
user output |
---|
(empty) |
Test 55
Verdict: TIME LIMIT EXCEEDED
input |
---|
874 13 |
correct output |
---|
RRRRRRRRRRRRDLLLLLLLLLLLDRRRRR... |
user output |
---|
(empty) |
Test 56
Verdict: TIME LIMIT EXCEEDED
input |
---|
12 366 |
correct output |
---|
DDDDDDDDDDDRUUUUUUUUUURDDDDDDD... |
user output |
---|
(empty) |