Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1559

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1559

2048

 

By Gabriel Dalalio, ITA BR 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;

int readInt()
{
    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;
    n = readInt();
    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++) {
                matrix[i][j] = readInt();
                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 & Try With Live Editor

Input

x
+
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

x
+
cmd
DOWN LEFT UP
RIGHT UP
NONE
Advertisements

Demonstration


Previous
#1558 Beecrowd Online Judge Solution 1558 Sum of Two Squares Solution in C, C++, Java, Js and Python
Next
#1561 Beecrowd Online Judge Solution 1561 Binary Watch Solution in C, C++, Java, Js and Python