CSES - Datatähti 2021 alku - Results
Submission details
Task:Ratsun reitit
Sender:Joo
Submission time:2020-10-02 14:33:13 +0300
Language:Java
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED27
#2ACCEPTED31
#3ACCEPTED42
Test results
testverdicttimegroup
#1ACCEPTED0.21 s1, 2, 3details
#2ACCEPTED0.21 s1, 2, 3details
#3ACCEPTED0.22 s1, 2, 3details
#4ACCEPTED0.21 s1, 2, 3details
#5ACCEPTED0.22 s1, 2, 3details
#6ACCEPTED0.21 s1, 2, 3details
#7ACCEPTED0.22 s1, 2, 3details
#8ACCEPTED0.22 s2, 3details
#9ACCEPTED0.25 s2, 3details
#10ACCEPTED0.25 s2, 3details
#11ACCEPTED0.30 s3details
#12ACCEPTED0.34 s3details
#13ACCEPTED0.34 s3details

Code

import java.util.Scanner;
import java.util.ArrayList;

public class RatsunReitit {

    private static final Scanner scanner = new Scanner(System.in);
    private static int boardSize;
    private static Node[][] board;

    public static void main(String[] args) {

        boardSize = scanner.nextInt();
        scanner.nextLine();

        board = new Node[boardSize][boardSize];

        for(int i = 0; i < boardSize; i++) {
            for(int j = 0; j < boardSize; j++) {
                board[i][j] = new Node(i, j);
            }
        }

        board[0][0].distance = 0;
        ArrayList<Node> nodesToCheck = new ArrayList<Node>();
        nodesToCheck.add(board[0][0]);

        while(!allNodesHaveBeenFound()) {
            ArrayList<Node> nodesFound = new ArrayList<Node>();
            for(Node node : nodesToCheck) {
                node.findAdjacentNodes(nodesFound);
            }
            nodesToCheck = nodesFound;
        }
        
        String s = "";
        for(int i = 0; i < boardSize; i++) {
            for(int j = 0; j < boardSize; j++) {
                s += board[i][j].distance + " ";
            }
            s += "\n";
        }
        System.out.print(s);
    }

    private static boolean allNodesHaveBeenFound() {
        for(int i = 0; i < boardSize; i++) {
            for(int j = 0; j < boardSize; j++) {
                if(board[i][j].distance == -1)
                    return false;
            }
        }
        return true;
    }

    private static class Node {

        public int distance;
        private int[] coords;

        public Node(int x, int y) {
            coords = new int[] {x, y};
            distance = -1;
        }

        public void findAdjacentNodes(ArrayList<Node> foundNodes) {

            int[][] adjacentNodes = new int[][] {
                {coords[0]+1, coords[1]+2},
                {coords[0]+2, coords[1]+1},
                {coords[0]+2, coords[1]-1},
                {coords[0]+1, coords[1]-2},
                {coords[0]-1, coords[1]-2},
                {coords[0]-2, coords[1]-1},
                {coords[0]-2, coords[1]+1},
                {coords[0]-1, coords[1]+2}
            };

            for(int[] nodeCoords : adjacentNodes) {
                if(nodeCoords[0] >= 0 && nodeCoords[0] < boardSize && nodeCoords[1] >= 0 && nodeCoords[1] < boardSize) {
                    Node currentlyCheckedNode = board[nodeCoords[0]][nodeCoords[1]];
                    if(currentlyCheckedNode.distance == -1) {
                        currentlyCheckedNode.distance = this.distance + 1;
                        foundNodes.add(currentlyCheckedNode);
                    }
                }
            }
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
4

correct output
0 3 2 5 
3 4 1 2 
2 1 4 3 
5 2 3 2 

user output
0 3 2 5 
3 4 1 2 
2 1 4 3 
5 2 3 2 

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
5

correct output
0 3 2 3 2 
3 4 1 2 3 
2 1 4 3 2 
3 2 3 2 3 
2 3 2 3 4 

user output
0 3 2 3 2 
3 4 1 2 3 
2 1 4 3 2 
3 2 3 2 3 
2 3 2 3 4 

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
6

correct output
0 3 2 3 2 3 
3 4 1 2 3 4 
2 1 4 3 2 3 
3 2 3 2 3 4 
2 3 2 3 4 3 
...

user output
0 3 2 3 2 3 
3 4 1 2 3 4 
2 1 4 3 2 3 
3 2 3 2 3 4 
2 3 2 3 4 3 
...

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
7

correct output
0 3 2 3 2 3 4 
3 4 1 2 3 4 3 
2 1 4 3 2 3 4 
3 2 3 2 3 4 3 
2 3 2 3 4 3 4 
...

user output
0 3 2 3 2 3 4 
3 4 1 2 3 4 3 
2 1 4 3 2 3 4 
3 2 3 2 3 4 3 
2 3 2 3 4 3 4 
...
Truncated

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
8

correct output
0 3 2 3 2 3 4 5 
3 4 1 2 3 4 3 4 
2 1 4 3 2 3 4 5 
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5 
...

user output
0 3 2 3 2 3 4 5 
3 4 1 2 3 4 3 4 
2 1 4 3 2 3 4 5 
3 2 3 2 3 4 3 4 
2 3 2 3 4 3 4 5 
...
Truncated

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
9

correct output
0 3 2 3 2 3 4 5 4 
3 4 1 2 3 4 3 4 5 
2 1 4 3 2 3 4 5 4 
3 2 3 2 3 4 3 4 5 
2 3 2 3 4 3 4 5 4 
...

user output
0 3 2 3 2 3 4 5 4 
3 4 1 2 3 4 3 4 5 
2 1 4 3 2 3 4 5 4 
3 2 3 2 3 4 3 4 5 
2 3 2 3 4 3 4 
...
Truncated

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
10

correct output
0 3 2 3 2 3 4 5 4 5 
3 4 1 2 3 4 3 4 5 6 
2 1 4 3 2 3 4 5 4 5 
3 2 3 2 3 4 3 4 5 6 
2 3 2 3 4 3 4 5 4 5 
...

user output
0 3 2 3 2 3 4 5 4 5 
3 4 1 2 3 4 3 4 5 6 
2 1 4 3 2 3 4 5 4 5 
3 2 3 2 3 4 3 4 5 6 
2 3 2 
...
Truncated

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
25

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
49

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
50

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 11

Group: 3

Verdict: ACCEPTED

input
75

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 12

Group: 3

Verdict: ACCEPTED

input
99

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated

Test 13

Group: 3

Verdict: ACCEPTED

input
100

correct output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...

user output
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 ...
Truncated