这个问题是只能用暴力做吗？

Question

这个问题是只能用暴力吗？如果不是，有没有人能提供一下思路？

2048 移动

时间限制：1.0s 内存限制：256.0MB 代码提交间隔：1分钟(现在可以提交)
试题来源：rookiepig
问题描述
《2048》是一款比较流行的数字游戏，最早于2014年3月20日发行。原版2048首先在GitHub上发布，原作者是Gabriele Cirulli，后被移植到各个平台。

游戏的玩法可以简单描述如下：

玩家进入游戏会看到一个方形棋盘格子，每个棋盘格子可以看作一个方块，有的格子会有数字，有的格子为空。标准版本的《2048》玩家开始时会有个方块是数字。
每次可以选择上下左右其中一个方向去滑动，每滑动一次，所有的数字方块都会朝滑动的方向靠拢，系统会在空白的地方随机出现一个新的数字方块（标准版本随机出现的新方块为数字，随着移动步数变大会出现、等方块）。相同数字的方块在靠拢相撞时会相加（注意：一次移动相邻的方块最多只能合并一次，认真观察下面例子中最后一行在向右移动后的棋盘变化情况）。不断的叠加最终拼凑出2048这个数字就算成功。
我们可以用一个二维数组表示棋盘格子的状态，举个棋盘大小的移动例子，代表空白的方块，为了简化问题我们暂不考虑随机产生新的方块。

假设当前棋盘状态：
2 0 0 0
0 2 2 0
0 2 2 2
2 2 2 2
Data
第一步选择向右移动，棋盘状态变为：
0 0 0 2
0 0 0 4
0 0 2 4
0 0 4 4
Data
第二步选择向下移动，棋盘状态变为：
0 0 0 0
0 0 0 2
0 0 2 4
0 0 4 8
Data
现在小明想自己在命令行界面下制作一个《2048》的游戏，第一步就是要实现棋盘的移动操作，他不会写程序，想寻求你的帮助。

输入格式
输入数据依次包括三部分：

输入整数 ，代表棋盘大小（）；
接下来会有 个非负整数（不大于1000），以二维数组的格式输入，代表棋盘状态；
接下来输入一个字符，表示一步移动的方向，字符只能是中的一种：
U --> 向上移动
D --> 向下移动
L --> 向左移动
R --> 向右移动
Data
输出格式
按照矩阵的格式输出移动后的棋盘状态（参考样例格式）。

注意：为了在矩阵下对齐多位数字，请使用C语言printf("%5d", num)做格式化输出，样例代码：

for (int r = 0; r < n; ++r) {
    for (int c = 0; c < n; ++c) {
        printf("%5d", a[r][c]);
    }
    printf("\n");
}

样例输入1
4
0 2 2 0
0 0 0 2
2 2 2 0
2 2 2 2
U
Data
样例输出1
4 4 4 4
0 2 2 0
0 0 0 0
0 0 0 0
Data
样例输入2
3
8 1 4
1 4 7
6 5 0
D
Data
样例输出2
8 1 0
1 4 4
6 5 7

我用暴力尝试过了，写了好几百行，崩溃了，求各位帮给蒟蒻讲讲思路。

Answer 1

因为四个方向的算法是相似的，可以共用，我的思路是用指针作为循环控制变量，于是指针指向行和列就会有不同结果，用step变量作为每次循环递增的值。代码如下：

#include<stdio.h>
#include<malloc.h>

int main() {
    int **a, n, last, *line, ln;
    int r, c, *i, *j, start,end, step;
    char dir;
    scanf("%d", &n);
    a = (int**)malloc(sizeof(int*)*n);
    line = (int*)malloc(sizeof(int) * n);
    for (r = 0; r < n; r++) {
        a[r] = (int*)malloc(sizeof(int) * n);
        for (c = 0; c < n; c++) {
            scanf("%d", a[r] + c);
        }
    }
    getchar();
    dir = getchar();
    switch (dir) {
        case 'U':
            //沿列“扫描”，从小到大 
            start=0;
            end=n;
            step=1;
            i=&c;
            j=&r; 
            break;
        case 'D':
            //沿列“扫描”，从大到小 
            start=n-1;
            end=-1;
            step=-1;
            i=&c;
            j=&r; 
            break;
        case 'L':
            //沿行“扫描”，从小到大
            start=0;
            end=n;
            step=1;
            i=&r;
            j=&c; 
            break;
        case 'R':
            //沿行“扫描”，从大到小 
            start=n-1;
            end=-1;
            step=-1;
            i=&r;
            j=&c; 
            break;
    }
    for (*i =start; *i != end; *i += step) {
        ln = 0;
        last=0;
        for (*j = start; *j != end; *j += step) {
            if(a[r][c]){
                if(last){
                    if(a[r][c]==last){
                        line[ln++]=last+a[r][c];
                        last=0;
                    }else{
                        line[ln++]=last;
                        last=a[r][c];
                    }
                }else{
                    last=a[r][c];
                }
            }
        }
        if(last)line[ln++]=last;
        for(;ln<n;ln++){
            line[ln]=0;
        }
        *j=start+ln*step;
        while(ln-->0){
            *j-=step;
            a[r][c]=line[ln];
        }
    }
    
    for (r = 0; r < n; r++) {
        for(c=0;c<n;c++){
            printf("%5d",a[r][c]);
        }
        printf("\n");
        free(a[r]);
    }
    free(a);
    free(line);
    return 0;
}