CSES - Datatähti 2021 alku - Results
Submission details
Task:Ratsun reitit
Sender:sumit_kk10
Submission time:2020-09-30 08:58:32 +0300
Language:C++ (C++11)
Status:READY
Result:58
Feedback
groupverdictscore
#1ACCEPTED27
#2ACCEPTED31
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s2, 3details
#9ACCEPTED0.09 s2, 3details
#10ACCEPTED0.09 s2, 3details
#11ACCEPTED0.44 s3details
#12--3details
#13--3details

Compiler report

input/code.cpp: In function 'int minStepToReachTarget(int*, int*, int)':
input/code.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <bits/stdc++.h> 
using namespace std; 
  
// structure for storing a cell's data 
struct cell { 
    int x, y; 
    int dis; 
    cell() {} 
    cell(int x, int y, int dis) 
        : x(x), y(y), dis(dis) 
    { 
    } 
}; 
  
// Utility method returns true if (x, y) lies 
// inside Board 
bool isInside(int x, int y, int N) 
{ 
    if (x >= 1 && x <= N && y >= 1 && y <= N) 
        return true; 
    return false; 
} 
  
// Method returns minimum step 
// to reach target position 
int minStepToReachTarget( int knightPos[], int targetPos[], int N){ 
    // x and y direction, where a knight can move 
    int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 }; 
    int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 }; 
  
    // queue for storing states of knight in board 
    queue<cell> q; 
  
    // push starting position of knight with 0 distance 
    q.push(cell(knightPos[0], knightPos[1], 0)); 
  
    cell t; 
    int x, y; 
    bool visit[N + 1][N + 1]; 
  
    // make all cell unvisited 
    for (int i = 1; i <= N; i++) 
        for (int j = 1; j <= N; j++) 
            visit[i][j] = false; 
  
    // visit starting state 
    visit[knightPos[0]][knightPos[1]] = true; 
  
    // loop untill we have one element in queue 
    while (!q.empty()) { 
        t = q.front(); 
        q.pop(); 
  
        // if current cell is equal to target cell, 
        // return its distance 
        if (t.x == targetPos[0] && t.y == targetPos[1]) 
            return t.dis; 
  
        // loop for all reachable states 
        for (int i = 0; i < 8; i++) { 
            x = t.x + dx[i]; 
            y = t.y + dy[i]; 
  
            // If reachable state is not yet visited and 
            // inside board, push that state into queue 
            if (isInside(x, y, N) && !visit[x][y]) { 
                visit[x][y] = true; 
                q.push(cell(x, y, t.dis + 1)); 
            } 
        } 
    } 
} 
int main() 
{ 
    int n;
    cin >> n;
    int knightPos[] = { 1, 1 }; 
    for(int i = 1; i <= n ; ++i){
    	for(int j = 1; j <= n; ++j){
    		int targetPos[] = {i, j};
    		cout << minStepToReachTarget(knightPos, targetPos, n) << " ";
		}
		cout << "\n";
    }
    return 0; 
} 

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:

input
99

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

user output
(empty)

Test 13

Group: 3

Verdict:

input
100

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

user output
(empty)