COCI '11 Contest 1 #6 Skakac

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.5s
Memory limit: 64M

Problem type

Mirko and Slavko are playing the popular new game known as The Knight. Mirko places a knight chess piece on an N \times N chessboard and, with Slavko blindfolded, makes exactly T moves, one per second. After that, Slavko must guess the final position of the knight in order to win.

The chessboard in this game is unusual in that each square is blocked part of the time. More precisely, each square is labelled by a positive integer. A square labelled by number K is clear only during seconds 0, K, 2K, 3K etc; it is blocked at all other times. The knight can, of course, occupy a square only while the square is clear.

The game begins in second 0. In each second Mirko must make a move (selecting one of 8 possible L-shaped moves, two squares in one direction and one square in the other, as per standard chess rules), provided that the destination square is not blocked during the next second. Help Slavko by writing a program to calculate all possible squares that the knight can possibly occupy after T moves.

Input Specification

The first line of input contains two positive integers, N (3 \le N \le 30), the size of the chessboard, and T (1 \le T \le 1\,000\,000), the number of moves that Mirko will make.

The second line of input contains two positive integers X and Y (1 \le X, Y \le N), the row and column indices of the knight's starting square selected by Mirko.

The next N lines each contain N positive integers less than 10^9 (one billion), the values of K for the corresponding chessboard squares.

Output Specification

The first line of output must contain the nonnegative integer M, the number of squares that the knight can possibly occupy after T moves.

The next M lines must contain indices of those squares, sorted by increasing row index, with cells in the same row sorted by increasing column index.

Scoring

In test cases worth 40\% of total points, the number of moves T will be less than 50\,000.

Sample Input 1

3 2
1 1
1 3 2
2 3 2
3 1 1

Sample Output 1

2
1 1
1 3

Explanation for Sample Output 1

The state of the chessboard in each second is shown below. Clear cells are denoted by ., blocked cells by #, and possible locations of the knight by K.

0^\text{th} second 1^\text{st} second 2^\text{nd} second
K..
...
...
.##
###
#K.
K#K
.#.
#..

Sample Input 2

5 6
2 3
4 5 3 2 3
1 3 4 3 1
3 4 1 3 2
4 4 2 1 3
4 6 4 9 2

Sample Output 2

5
1 4
2 1
2 5
4 5
5 2

Sample Input 3

3 3
2 2
3 6 4
2 2 5
1 3 7

Sample Output 3

0

Comments

There are no comments at the moment.