— Dark mode

Putka Open 2020 – 4/5

Ruudukko

  • Start: 2020-11-06 18:00:00
  • End: 2020-11-08 23:00:00
Submission details
Task:Ruudukko
Sender:rasastusni
Submission time:2020-11-08 20:20:11 +0200
Language:C++ (C++17)
Status:READY
Result:17
Feedback
groupverdictscore
#1ACCEPTED5
#2ACCEPTED12
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 5details
#2ACCEPTED0.01 s2, 5details
#3--3, 5details
#4--4, 5details
#5--5details
#6--5details
#7ACCEPTED0.01 s2, 5details
#8ACCEPTED0.01 s2, 5details
#9ACCEPTED0.01 s3, 5details
#10ACCEPTED0.01 s3, 5details
#11ACCEPTED0.01 s3, 5details
#12ACCEPTED0.01 s3, 5details
#13ACCEPTED0.01 s4, 5details
#14--5details
#15--3, 5details
#16--5details

Code

#include <iostream>
#include <string>

using namespace std;

bool board[50][50] = {false};
char desc[50*50] = {0};
int n, m;
int startx, starty;
int endx, endy;

void print() {
	for (int i = 0; i < n; ++i) {
		for (int a = 0; a < m; ++a) {
			cout << board[i][a];
		}
		cout << endl;
	}
}

bool deadend(int x, int y) {
	if (board[y][x]) return false;
	if (x == endx && y == endy) return false;
	int blocks = 0;
	if (x == 0 || board[y][x-1]) ++blocks;
	if (x == m-1 || board[y][x+1]) ++blocks;
	if (y == 0 || board[y-1][x]) ++blocks;
	if (y == n-1 || board[y+1][x]) ++blocks;
	return blocks == 3;
}

int solve(int d, int x, int y) {
	if (x == endx && y == endy && d == n*m-1) {
		desc[d] = 0;
		return 1;
	}
	if (x < 0 || y < 0 || x >= m || y >= n || board[y][x]) return 0;
	//if (x == 0 && y == 6) return 0;
	board[y][x] = true;
	bool mr = (x == m-1) ? false : deadend(x+1, y);
	bool ml = (x == 0) ? false : deadend(x-1, y);
	bool md = (y == n-1) ? false : deadend(x, y+1);
	bool mt = (y == 0) ? false : deadend(x, y-1);
	if (!ml && !md && !mt) {
		desc[d] = 'R';
		if (solve(d+1, x+1, y)) return 1;
	}
	if (!mr && !md && !mt) {
		desc[d] = 'L';
		if (solve(d+1, x-1, y)) return 1;
	}
	if (!mr && !ml && !mt) {
		desc[d] = 'D';
		if (solve(d+1, x, y+1)) return 1;
	}
	if (!mr && !ml && !md) {
		desc[d] = 'U';
		if (solve(d+1, x, y-1)) return 1;
	}
	board[y][x] = false;
	return 0;
}

int main(int argc, char* argv[])
{
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		cin >> n >> m >> starty >> startx >> endy >> endx;
		--starty; --startx; --endy; --endx;
		if (solve(0, startx, starty)) {
			cout << "YES" << endl;
			cout << desc << endl;
		} else {
			cout << "NO" << endl;
		}
		for (int y = 0; y < n; ++y) {
			for (int x = 0; x < m; ++x) {
				board[y][x] = false;
			}
		}
	}
}

Test details

Test 1

Group: 1, 5

Verdict: ACCEPTED

input
100
1 45 1 45 1 1
1 18 1 1 1 10
1 47 1 17 1 30
1 33 1 28 1 20
...
view save

correct output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...
view save

user output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...
Truncated

Test 2

Group: 2, 5

Verdict: ACCEPTED

input
100
2 43 1 33 1 21
2 2 1 1 2 2
2 32 1 1 2 8
2 14 1 12 1 14
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
NO
NO
NO
NO
YES
...
Truncated

Test 3

Group: 3, 5

Verdict:

input
100
3 4 2 1 2 4
3 38 2 24 1 22
3 29 2 23 2 3
3 8 3 1 1 2
...
view save

correct output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...
view save

user output
(empty)

Test 4

Group: 4, 5

Verdict:

input
100
4 25 2 19 1 5
4 13 3 10 4 12
4 7 3 1 4 2
4 23 1 19 2 5
...
view save

correct output
YES
DDRRRRRRULLLLLURRRRRULLLLLLLDD...
view save

user output
(empty)

Test 5

Group: 5

Verdict:

input
100
16 8 13 1 14 8
41 21 19 11 32 12
46 17 13 7 6 11
8 41 4 32 4 12
...
view save

correct output
NO
YES
LURULURULURULURULURRDDDDDDDDDR...
view save

user output
(empty)

Test 6

Group: 5

Verdict:

input
100
31 38 18 35 31 37
35 48 7 13 21 21
46 21 25 2 4 19
35 2 13 2 35 1
...
view save

correct output
YES
LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...
view save

user output
(empty)

Test 7

Group: 2, 5

Verdict: ACCEPTED

input
100
2 4 1 3 1 4
2 4 2 2 1 1
2 4 2 3 1 2
2 4 2 3 1 4
...
view save

correct output
YES
LLDRRRU
NO
NO
NO
...
view save

user output
YES
LLDRRRU
NO
NO
NO
...
Truncated

Test 8

Group: 2, 5

Verdict: ACCEPTED

input
100
2 5 1 2 2 4
2 5 1 2 1 1
2 5 2 1 1 2
2 5 1 1 1 5
...
view save

correct output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...
view save

user output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...
Truncated

Test 9

Group: 3, 5

Verdict: ACCEPTED

input
100
3 4 1 1 2 3
3 4 2 4 3 2
3 4 2 1 3 1
3 4 1 4 3 4
...
view save

correct output
YES
DDRRRUULLDR
NO
YES
URRRDDLULDL
...
view save

user output
YES
RRRDDLLLURR
NO
YES
URRRDDLULDL
...
Truncated

Test 10

Group: 3, 5

Verdict: ACCEPTED

input
100
3 5 3 4 3 2
3 5 3 5 2 3
3 5 3 1 2 2
3 5 3 1 3 2
...
view save

correct output
NO
NO
YES
UURRRRDDLULDLU
NO
...
view save

user output
NO
NO
YES
RRRRUULDLULLDR
NO
...
Truncated

Test 11

Group: 3, 5

Verdict: ACCEPTED

input
100
3 8 2 8 1 2
3 8 2 4 1 7
3 8 3 4 2 7
3 8 2 5 3 1
...
view save

correct output
NO
NO
NO
YES
LLLDRRRRURDRUULLLLLLLDD
...
view save

user output
NO
NO
NO
YES
LLLLURRRRRRRDDLULDLLLLL
...
Truncated

Test 12

Group: 3, 5

Verdict: ACCEPTED

input
100
3 9 1 3 2 9
3 9 1 6 1 5
3 9 3 6 2 8
3 9 3 2 3 4
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
Truncated

Test 13

Group: 4, 5

Verdict: ACCEPTED

input
100
4 4 2 2 1 4
4 4 4 1 2 2
4 4 2 1 4 3
4 4 3 1 3 3
...
view save

correct output
YES
DDLUUURRDDDRUUU
YES
UUURRRDLDRDLLUU
NO
...
view save

user output
YES
RRDDLULDLUUURRR
YES
RRRULLLUURRRDLL
NO
...
Truncated

Test 14

Group: 5

Verdict:

input
100
12 27 6 22 1 8
6 25 3 2 4 4
6 16 4 6 5 2
36 33 8 6 1 6
...
view save

correct output
YES
DLDDDDDRUUUURDDDDRUURDDRRULURU...
view save

user output
(empty)

Test 15

Group: 3, 5

Verdict:

input
100
3 12 3 5 1 4
3 20 3 19 2 19
3 34 3 9 2 9
3 38 2 15 3 15
...
view save

correct output
YES
RRRRRRRUULDLULDLULDLULDLDLULDL...
view save

user output
(empty)

Test 16

Group: 5

Verdict:

input
100
50 50 29 1 16 21
50 50 37 5 23 48
50 50 32 22 45 24
50 50 6 28 12 37
...
view save

correct output
YES
DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...
view save

user output
(empty)

Tasks

A Neliöt-B Peli-C Tekijät-D Ruudukko-

Submissions (rasastusni)

2020-11-08 20:27:03 172020-11-08 20:20:11 172020-11-08 20:18:53 5