Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1559

2048

By Gabriel Dalalio, ITA Brazil

Timelimit: 1

This year, the game known as 2048 has become very popular on the internet . Here is a screenshot of the game:

The arrow keys are used to perform moves (up, down, left and right). Every time a key is pressed, the numbered blocks try to slide in the matrix if there is space. In the example image, if the left key is pressed, 5 blocks will move (8, 2, 16, 2, 32).

Besides of trying to slide, adjacent blocks with the same number come together in a single block with a doubled number if they try to slide in the right direction. In the example image, if the down key is pressed, two blocks 2 will turn into a block 4 and two blocks 32 will turn into a block 64.

During the game, in addition to the plays, blocks containing powers of 2 appear randomly in the matrix. The goal is to join the blocks to form a block with the number 2048. When this happens, the player wins the game and cannot make any more moves.

However, it can also happen that the player is left without possible moves before forming the number 2048. In the example image, press the right key is not a legal move, since no block can move or join another block.

Your task in this problem is to say which moves is valid for a given state of the game.

Input

The input starts with a line containing the number of test cases. For each test case, the input consists of 4 lines containing a square array of size 4. Matrix numbers are equal to 0 to indicate that no block is in the position, or are equal to powers of 2 between 2 and 2048 inclusive.

Output

For each test, the output consists of one line containing all possible moves for the given state of the game. The moves are indicated by DOWN, LEFT, RIGHT and UP. The moves should be written in alphabetical order. If there is no possible move, print NONE.

 Sample Input Sample Output 3 0 0 0 8 0 0 2 16 0 0 2 32 2 8 16 32 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 4 8 16 4 8 16 32 8 16 32 64 16 32 64 128 DOWN LEFT UP RIGHT UP NONE

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <locale>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define FOR(i, a, b) for (int i = a; i  < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i  <  N; ++i)
#define MAX 110
#define pb push_back
#define mp make_pair

using namespace std;

const double pi = acos(-1.0);

struct pt;
typedef pair < pt, pt> line;
typedef vector<pt> polygon;
typedef pair < pt, int> ddi;
typedef pair dd;
typedef pair < string, string> ss;

{
bool minus = false;
int result = 0;
char ch = getchar_unlocked();
while (true) {
if (ch == '-')
break;
if (ch >= '0' && ch  < = '9')
break;
ch = getchar_unlocked();
}
if (ch == '-')
minus = true;
else
result = ch - '0';
while (true) {
ch = getchar_unlocked();
if (ch  <  '0' || ch > '9')
break;
result = result * 10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}

int matrix[4][4];
int dir[][2] = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } };
set < string> resp;
vector<string> bib;

void hasMovement(int x, int y)
{
for (int i = 0; i  <  4; i++) {
int x1 = x + dir[i][0];
int y1 = y + dir[i][1];
if (x1  <  0 || x1 >= 4 || y1 < 0 || y1 >= 4)
continue;
if (matrix[x][y] == matrix[x1][y1])
resp.insert(bib[i]);
else if (!matrix[x1][y1])
resp.insert(bib[i]);
}
}

int main()
{
int n;
bib.pb("DOWN");
bib.pb("LEFT");
bib.pb("RIGHT");
bib.pb("UP");
while (n--) {
bool flag = false;
for (int i = 0; i  <  4; i++)
for (int j = 0; j  <  4; j++) {
if (matrix[i][j] == 2048)
flag = true;
}

if (!flag)
for (int i = 0; i  <  4; i++)
for (int j = 0; j  <  4; j++)
if (matrix[i][j])
hasMovement(i, j);
if (resp.size()) {
set < string>::iterator it;
for (it = resp.begin(); it != resp.end(); it++)
if (it != resp.begin())
printf(" %s", (*it).c_str());
else
printf("%s", (*it).c_str());
printf("\n");
} else
printf("NONE\n");
resp.clear();
}
return 0;
}
``````
Copy The Code &

Input

cmd
3
0 0 0 8
0 0 2 16
0 0 2 32
2 8 16 32
0 0 0 0
0 0 0 0
0 0 0 0
2 0 0 0
2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128

Output

cmd
DOWN LEFT UP
RIGHT UP
NONE