MKJUMPS - Making Jumps


A knight is a piece used in the game of chess. The chessboard itself is square array of cells. Each time a knight moves, its resulting position is two rows and one column, or two columns and one row away from its starting position. Thus a knight starting on row r, column c – which we’ll denote as (r, c) – can move to any of the squares (r-2,c-1), (r-2,c+1), (r-1,c-2), (r-1,c+2), (r+1,c-2), (r+1,c+2), (r+2,c-1), or (r+2,c+1). Of course, the knight may not move to any square that is not on the board.

Suppose the chessboard is not square, but instead has rows with variable numbers of columns, and with each row offset zero or more columns to the right of the row above it. The figure to the left illustrates one possible configuration. How many of the squares in such a modified chessboard can a knight, starting in the upper left square (marked with an asterisk), not reach in any number of moves without resting in any square more than once?

subir imagenes

If necessary, the knight is permitted to pass over regions that are outside the borders of the modified chessboard, but as usual, it can only move to squares that are within the borders of the board.

Input

There will be multiple cases to consider. The input for each case begins with an integer n, between 1 and 10, that specifies the number of rows in the modified chessboard. Following n there will be n pairs of integers, with the ith pair corresponding to the ith row of the chessboard. The first integer of each pair indicates the number of squares skipped at the beginning of the row. The second integer indicates the number of squares in the row (which will always be at least 1).The last case will be followed by the integer 0.

For example, input for the case illustrated by the chessboard shown above would be:

7 0 3 0 3 0 4 0 4 1 3 1 7 4 4

The maximum dimensions of the board will be 10 rows and 10 columns. That is, any modified chessboard specified by the input will fit completely on a 10 row, 10 column board.

Output

For each input case, display the case number (1, 2, …), and the number of squares that the knight can not reach. Display the results in the format shown in the examples below.

Example

Input:
7 0 3 0 3 0 4 0 4 1 3 1 7 4 4
3 0 3 0 3 0 3
2 0 1 2 1
0

Output:
Case 1, 4 squares can not be reached.
Case 2, 1 square can not be reached.
Case 3, 0 squares can not be reached.

hide comments
rexomnia: 2022-12-06 16:47:39

in output, 'c' of case should be capital, fucking capital!!!!!!!!!!!!!!!!!

tactile_blue: 2022-04-09 16:18:23

The language is a bit misleading IMAO!
"How many of the squares in such a modified chessboard can a knight, starting in the upper left square (marked with an asterisk), not reach in any number of moves without resting in any square more than once?", what the question actually wants is the minimum no. of squares the horse can not cover in "one continuous" series of jumps without crossing any square twice.
I got this from the github repo of xamitksx. I too was getting output of first test case 0 initially cause my code was calculating the no. of squares that the knight can't go in all possible jumps which is not what the question is asking.

khoaph: 2021-10-22 14:03:54

Thanks to Amaroq! Without your explaination, I can not have solved this problem after a lot of WA

aidoaido: 2021-04-01 12:39:17

on this side, i don't know writing english, therefore check gramar on my comment

recs34: 2019-10-29 20:48:04

...offset zero or more columns to the right of the row above it ... read it carefully

Last edit: 2019-10-29 21:30:17
scolar_fuad: 2019-04-19 11:00:09

suggest me any blog to learn backtracking

f00zz: 2019-04-01 14:08:31

I'm curious to know whether there's a better way to solve this without enumerating all possible paths with backtracking. This approach works with the test cases, but obviously wouldn't work with a test case like 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10 0 10

Last edit: 2019-04-02 02:07:13
divyansh_soni: 2018-10-03 17:20:03

got wrong answer 3 times just by printing 1 squares , haha...

phoemur: 2018-09-10 01:56:13

AC in std::numeric_limits<unsigned long long>::max() go !!!

anushka_ahuja: 2018-06-25 22:00:44

Ac in one go!!
First backtracking problem.
My 60th!!


Added by:Camilo Andrés Varela León
Date:2007-05-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:North Central North America Regional Programming Contest - 2003