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 
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;
}
Input
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
RIGHT UP
NONE