题解：P8232 [AGM 2022 资格赛] 2048 花园

· · 题解

洛谷P8232

题目描述

给出一个 n \times m 的矩阵，进行 k 次操作，每次操作开始时会将行号最小且最靠左的一个空格子（也就是数字为 0 的格子）改为 1，然后选择上/下/左/右四个方向中的一个，使格子按照这个方向进行移动和合并。

如果操作开始时没有空格子，则停止操作。

设矩阵中的最大值是 s，则问在最多经过最多 k 次操作所产生的最多 4^k 个矩阵中的 s 的最大值。

分析操作

操作前将行号最小且最靠左的一个空格子改为 1 的操作不难理解，就是在所有空格子 a_{i,j} 中，在 i 最小的前提下 j 最小的格子，可以直接遍历寻找。

那格子的移动和合并怎样理解呢？

拿左方向举个例子

0 0 2 1 0 1 2

首先是移动，如果 a_{i,j} 非空且 a_{i,j-1} 是空格子，那么就交换位置。

2 1 1 2 0 0 0

之后是合并，如果 a_{i,j}=a_{i,j+1}，则 a_{i,j}+1,a_{i,j+1}=0。

2 2 0 2 0 0 0

显然这时可以继续重复移动和合并的操作。

3 2 0 0 0 0 0

这就是最终操作结束后的结果。

思路

注意到 1 \le n,m,\le 2500,n\times m\le 2500,1\le k\times k\le \min(n,m)，所以 \min(n,m)\le 50,k\le 7。

由于 k 很小，考虑暴力进行模拟，将最多 4^7 种情况枚举出来。

实现方法

对于将空格子变为 1 的操作，直接遍历矩阵寻找。

bool flag1=0;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(a[i][j]==0)
        {
            a[i][j]=1;
            flag1=1;
            break;
        }
    }
    if(flag1) break;
}

其次对于移动和合并，可以将矩阵视为是一些互不相干的一维数组，分别处理。

在处理过程中，可以无限循环进行处理，直到无法移动时跳出循环。

再次拿左方向举例

for(int i=1;i<=n;i++)
{
    while(true)
    {
        bool flag=1;
        for(int j=1;j<m;j++)
        {
            if(a[i][j]==0&&a[i][j+1])//移动
            {
                swap(a[i][j],a[i][j+1]);
                flag=0;
            }
            else if(a[i][j]&&a[i][j]==a[i][j+1])//合并
            {
                a[i][j]++;
                a[i][j+1]=0;
                flag=0;
            }
        }
        if(flag) break;
    }
}

深搜时不要忘记回溯。

同时注意到数据的组数不确定，那么就可以运用一些小技巧。

while(cin>>n>>m>>k)

代码

请勿抄袭。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k;
ll a[2550][2550];
ll ans;
void dfs(int cnt)
{
    if(cnt>k)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                ans=max(ans,a[i][j]);
        return;
    }
    bool flag1=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                a[i][j]=1;
                flag1=1;
                break;
            }
        }
        if(flag1) break;
    }
    if(!flag1)
    {
        dfs(k+1);
        return;
    }
    ll ta[2550][2550];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ta[i][j]=a[i][j];
    for(int i=1;i<=n;i++)
    {
        while(true)
        {
            bool flag=1;
            for(int j=1;j<m;j++)
            {
                if(a[i][j]==0&&a[i][j+1])
                {
                    swap(a[i][j],a[i][j+1]);
                    flag=0;
                }
                else if(a[i][j]&&a[i][j]==a[i][j+1])
                {
                    a[i][j]++;
                    a[i][j+1]=0;
                    flag=0;
                }
            }
            if(flag) break;
        }
    }
    dfs(cnt+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=ta[i][j];
    for(int i=1;i<=n;i++)
    {
        while(true)
        {
            bool flag=1;
            for(int j=m;j>1;j--)
            {
                if(a[i][j]==0&&a[i][j-1])
                {
                    swap(a[i][j],a[i][j-1]);
                    flag=0;
                }
                else if(a[i][j]&&a[i][j]==a[i][j-1])
                {
                    a[i][j]++;
                    a[i][j-1]=0;
                    flag=0;
                }
            }
            if(flag) break;
        }
    }
    dfs(cnt+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=ta[i][j];
    for(int j=1;j<=m;j++)
    {
        while(true)
        {
            bool flag=1;
            for(int i=1;i<n;i++)
            {
                if(a[i][j]==0&&a[i+1][j])
                {
                    swap(a[i][j],a[i+1][j]);
                    flag=0;
                }
                else if(a[i][j]&&a[i][j]==a[i+1][j])
                {
                    a[i][j]++;
                    a[i+1][j]=0;
                    flag=0;
                }
            }
            if(flag) break;
        }
    }
    dfs(cnt+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=ta[i][j];
    for(int j=1;j<=m;j++)
    {
        while(true)
        {
            bool flag=1;
            for(int i=n;i>1;i--)
            {
                if(a[i][j]==0&&a[i-1][j])
                {
                    swap(a[i][j],a[i-1][j]);
                    flag=0;
                }
                else if(a[i][j]&&a[i][j]==a[i-1][j])
                {
                    a[i][j]++;
                    a[i-1][j]=0;
                    flag=0;
                }
            }
            if(flag) break;
        }
    }
    dfs(cnt+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=ta[i][j];
}
int main()
{
    while(cin>>n>>m>>k)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        ans=0;
        dfs(1);
        cout<<ans<<'\n';
    }
    return 0;
}

这是本蒟蒻的第一篇题解，十分激动，代码若有不足，还请见谅。