Problem Description
Write a block moving program. A block is a k by k square in a 8 by 8 grid. The grid has 8 rows (from 0 to 7, top to bottom) and eight columns (from 0 to 7, left to right). A 2 by 2 block with its upper left corner located at row 3 and column 2 is like this.
00000000
00000000
00000000
00110000
00110000
00000000
00000000
00000000
We can represent a block with an unsigned long long integer, which has 64 bits, therefore the block above can be represented as a binary number like this. As a result, we can use fast bit operations, e.g., bitwise and/or and shifting, to implement the following operations (including the initialization of the grid). If you do not use bit operatios, it is very likely that your program will receive TLEs.
lowbit highbit
0 1 2 3 4 5 6
0123456789012345678901234567890123456789012345678901234567890123
0000000000000000000000000011000000110000000000000000000000000000
NOTE: Here the left-top digit on the 8 by 8 grid is the lowest bit of the integer.
Now given a block as an unsigned 64 bit integer, you need to implement the following functions.
void printBlock(unsigned long long int *block);
Print a block as indicated above.void initialize(unsigned long long int *block, int row, int column, int size);
This function will initialize the block so that the left upper corner is located at (row, column), and with size. For example, we can useinitialize(&block, 3, 2, 2)
to get the block in the previous example.int moveLeft(unsigned long long int *block);
This function will move the block left by one column. For example, if we callmoveLeft(&block)
then the block will look like this.00000000
00000000
00000000
01100000
01100000
00000000
00000000
00000000
int moveRight(unsigned long long int *block);
This function will move the block right by one column. For example, if we call moveRight(&block) then the block will look like this.00000000
00000000
00000000
00011000
00011000
00000000
00000000
00000000
int moveUp(unsigned long long int *block);
This function will move the block up by one row. For example, if we call moveUp(&block) then the block will look like this.00000000
00000000
00110000
00110000
00000000
00000000
00000000
00000000
int moveDown(unsigned long long int *block);
This function will move the block down by one row. For example, if we call moveDown(&block) then the block will look like this.00000000
00000000
00000000
00000000
00110000
00110000
00000000
00000000
Some moves may be invalid. For example, if the block is on row 0 then it cannot be moved up, and if is at column 0 then it cannot be moved left. A move function should return 1 if the move is valid, and 0 if the move is invalid. If the move is invalid, the value of the block should NOT be changed.
Source codes
main.c
1234567891011121314151617181920212223242526272829303132333435363738 #include <stdio.h>
#include "blockmover.h"
int
main() {
unsigned
long
long
int
num;
char
operation;
int
ret;
scanf
(
"%llu"
, &num);
while
(1) {
ret = 1;
scanf
(
"%c"
, &operation);
if
(operation ==
'p'
) {
printBlock(&num);
break
;
}
else
if
(operation ==
'u'
)
ret = moveUp(&num);
else
if
(operation ==
'd'
)
ret = moveDown(&num);
else
if
(operation ==
'l'
)
ret = moveLeft(&num);
else
if
(operation ==
'r'
)
ret = moveRight(&num);
else
if
(operation ==
'i'
) {
int
row, column, size;
scanf
(
"%d %d %d"
, &row, &column, &size);
initialize(&num, row, column, size);
}
if
(ret == 0)
printf
(
"Invalid move!\n"
);
}
return
0;
}
blockmover.h
123456 void
printBlock(unsigned
long
long
int
*block);
void
initialize(unsigned
long
long
int
*block,
int
row,
int
column,
int
size);
int
moveLeft(unsigned
long
long
int
*block);
int
moveRight(unsigned
long
long
int
*block);
int
moveUp(unsigned
long
long
int
*block);
int
moveDown(unsigned
long
long
int
*block);
blockmover.c
Here is the template code.
12345678910111213141516171819202122232425262728293031 #include <stdio.h>
// You can write your own functions here.
void
printBlock(unsigned
long
long
int
*block) {
// your implementation here
}
void
initialize(unsigned
long
long
int
*block,
int
row,
int
column,
int
size) {
// your implementation here
}
int
moveLeft(unsigned
long
long
int
*block) {
// your implementation here
return
0;
// You may change this return value.
}
int
moveRight(unsigned
long
long
int
*block) {
// your implementation here
return
0;
// You may change this return value.
}
int
moveUp(unsigned
long
long
int
*block) {
// your implementation here
return
0;
// You may change this return value.
}
int
moveDown(unsigned
long
long
int
*block) {
// your implementation here
return
0;
// You may change this return value.
}
Technical Specification and Constraints
- 20pt. Implement
printBlock
. - 15pt. Implement
printBlock
,moveLeft
, andmoveRight
. All moves are valid. - 20pt. Implement
printBlock
, and all four move functions. All moves are valid. - 30pt. Implement all four move and
initialize
functions. All moves are valid. - 15pt. Implement all four move and
initialize
functions. Some moves may be invalid.
Except illegal moves, all other inputs are valid.
Sample Inputs and Outputs
In input files, the first line is the initial value of block
. The following lines are actions. 'l'
means moving left, 'u'
means moving up, and so on. 'i'
means initialization. The three arguments of 'i'
command mean row, column and size. 'p'
prints the current block. Once 'p'
is called, the program ends.
Sample Input 1
123628217696256
l
u
p
Sample Output 1
00000000
00000000
00011100
00011100
00011100
00000000
00000000
00000000
Sample Input 2
0
i 4 0 4
l
r
p
Sample Output 2
Invalid move!
00000000
00000000
00000000
00000000
01111000
01111000
01111000
01111000
Hint
To initialize a 2 by 2 block we need to build the following pattern.
00000000
00000000
00000000
00000000
00000000
00000000
00000011
00000011
If we write it in binary it will become the following.
0000000000000000000000000000000000000000000000000000001100000011
To get this pattern we simply take them or of the following.
0000000000000000000000000000000000000000000000000000000000000011
0000000000000000000000000000000000000000000000000000001100000000
Then we can use moveUp and moveLeft to move the block into the correct position.
To detect the cases that we cannot move a block we need to detect whether the block is at row 0 or 7, or column 0, and 7, so we need the following four patterns.
11111111
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
11111111
10000000
10000000
10000000
10000000
10000000
10000000
10000000
10000000
00000001
00000001
00000001
00000001
00000001
00000001
00000001
00000001
It is easy to construct the first and second pattern, which is simply 255. In order to construct the fourth pattern, we consider its binary form.
0000000100000001000000010000000100000001000000010000000100000001
It is easy to see that it can be constructed by taking an "or" on the following.
0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000100000000
0000000000000000000000000000000000000000000000010000000000000000
0000000000000000000000000000000000000001000000000000000000000000
0000000000000000000000000000000100000000000000000000000000000000
0000000000000000000000010000000000000000000000000000000000000000
0000000000000001000000000000000000000000000000000000000000000000
0000000100000000000000000000000000000000000000000000000000000000
It is easy then to construct the third pattern from this.