# 50012. Block Mover with Bit Operations

## 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.

0000000000000000000000000011000000110000000000000000000000000000

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                                                   highbit0         1         2         3         4         5         601234567890123456789012345678901234567890123456789012345678901230000000000000000000000000011000000110000000000000000000000000000

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 use initialize(&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 call moveLeft(&block) then the block will look like this.

0000000000000000000000000110000001100000000000000000000000000000
• 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.

0000000000000000000000000001100000011000000000000000000000000000
• 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.

0000000000000000001100000011000000000000000000000000000000000000
• 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.

0000000000000000000000000000000000110000001100000000000000000000

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

123456void 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, and moveRight. 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

123628217696256lup

### Sample Output 1

0000000000000000000111000001110000011100000000000000000000000000

### Sample Input 2

0i 4 0 4lrp

### Sample Output 2

Invalid move!0000000000000000000000000000000001111000011110000111100001111000

## Hint

To initialize a 2 by 2 block we need to build the following pattern.

0000000000000000000000000000000000000000000000000000001100000011

If we write it in binary it will become the following.

0000000000000000000000000000000000000000000000000000001100000011

To get this pattern we simply take them or of the following.

00000000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000000000000000000000000001100000000

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.

1111111100000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000011111111 1000000010000000100000001000000010000000100000001000000010000000 0000000100000001000000010000000100000001000000010000000100000001

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.

00000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000

It is easy then to construct the third pattern from this.