Under construction

Still being built. Things may change

Super 2048 (Small)

Interview

Time limit5sMemory limit512 MB

Summary
The program slides all tiles of an N by N 2048 board one move in the given direction, merging equal pairs once with leading tiles first.
Level

Easy3 of 10

Topics
Simulation, Matrix
Solved
No attempts yet

Problem

2048 is a single player game. You slide tiles on a grid so that equal numbers merge, and the goal is to build a tile showing 2048.

The original game uses a 4 x 4 grid. In one move the player picks one of four directions, left, right, up, or down, and all tiles slide as far as they can in that direction at the same time. When two tiles holding the same number collide during the slide, they merge into one tile holding the sum. Within a single move a newly created tile never merges again, and merges happen first for the tiles that are farther ahead in the direction of movement. For example, if a row holds three 2s as "2 2 2" and the player moves left, the row becomes "4 2 0". The two leading 2s merge first.

The figure above shows how a 4 x 4 grid changes when the player moves every tile right.

Alice and Bob found this game by accident and liked the feeling of tiles merging. After a few rounds the board felt small, so they grew it to N x N and called the bigger game "Super 2048".

The larger board is hard to follow by eye. Write a program that computes the board after all tiles make one move in a given direction.

Input

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the side length of the board, N, and the direction the tiles move to, DIR, separated by a single space. DIR is one of "left", "right", "up", or "down".

The next N lines describe the original board. Each line holds N space separated integers and represents one row of the board, from top to bottom. Each integer is the value of the tile at that cell, and 0 means an empty cell.

Limits

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 10
  • Each number on the board is either 0 or a power of two between 2 and 1024, inclusive.

Output

For each test case, output one line containing "Case #x:", where x is the test case number starting from 1. Then output N more lines describing the board after the move, in the same format as the input. Each of those lines holds N space separated integers.

Examples2

  1. Example 1

    Input
    3
4 right
2 0 2 4
2 0 4 2
2 2 4 8
2 2 4 4
10 up
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 right
2 2 2
4 4 4
8 8 8
    Expected output
    Case #1:
0 0 4 4
0 2 4 2
0 4 4 8
0 0 4 8
Case #2:
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Case #3:
0 2 4
0 4 8
0 8 16

  2. Example 2

    Input
    4
4 left
2 2 2 2
4 4 4 4
2 2 4 4
2 4 2 4
4 right
2 2 2 2
4 4 4 4
2 2 4 4
2 4 2 4
4 up
2 4 2 2
2 4 4 4
2 4 2 2
2 4 4 4
4 down
2 4 2 2
2 4 4 4
2 4 2 2
2 4 4 4
    Expected output
    Case #1:
4 4 0 0
8 8 0 0
4 8 0 0
2 4 2 4
Case #2:
0 0 4 4
0 0 8 8
0 0 4 8
2 4 2 4
Case #3:
4 8 2 2
4 8 4 4
0 0 2 2
0 0 4 4
Case #4:
0 0 2 2
0 0 4 4
4 8 2 2
4 8 4 4