「ULSG-1」2048 题解

题目传送门

题目解析

玩一次就明白了。

传送门

解题思路

合并

从下往上，从左往右，对于每一个非零的数，向上第一个非零数，若与之相等，则此数与找到的数相加，同时分数加上合并后的数，而找到的数清零。若第一个非零数与它不相等，直接停止寻找过程，意为无法合并，等待下落。

下落

依旧从下往上，从左往右，对于每一个为零的数，向上寻找第一个非零的数，零的位置赋值为找到的第一个非零数，原非零数清零。

思路解释

从下往上行动是为了满足优先合并下面的数与合并后得数不能继续参与合并两个条件。每个数更新后因为以从下往上，从左往右的顺序不会进入第二次合并操作。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+1;
#define ll long long

int n;
ll a[N][N];
ll score;

int fs(ll x,ll i,ll j)//合并查找
{
	for(i--;i>=1;i--)
	{
		if(a[i][j]==x) return i;
		if(a[i][j]>0) return 0;
	}
	return 0;
}

int fss(ll i,ll j)//下落查找
{
	for(;i>=1;i--)
	{
		if(a[i][j]!=0) return i;
	}
	return 0;
}

void pr()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%lld ",a[i][j]);
		}
		printf("\n");
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%lld",&a[i][j]);
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=n;j++)
		{
			int p=fs(a[i][j],i,j);
			if(p)
			{
				a[i][j]+=a[p][j];
				score+=a[i][j];
				a[p][j]=0;
			}
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=n;j++)
		{
			if(!a[i][j])
			{
				int p=fss(i,j);
				a[i][j]=a[p][j];
				a[p][j]=0;
			}
		}
	}
	printf("%lld\n",score);
	pr();
	return 0;
}