题解 P8549 小挖的核燃料填充

· · 题解

不错的dfs练手题。因为作者的 dfs 很菜，所以我们从头讲起。

前情提要：这篇题解建议配合代码食用，可以根据题解一行一行理解代码，我基本上都有讲。

首先我们考虑怎么搜索。单独考虑每一个元素显然是困难的，但是题目给了 n\times n 个 n \times n 的矩阵，又因为每次旋转的时候是在一个将一个小矩阵作为整体旋转的，所以可以考虑把一个 n \times n 的小矩阵看作一个元素，这样的话会好搜索很多。

我们搜索的时候考虑传三个参数 x,y,s，分别代表着这个小矩阵的行、列、花费的代价。

小矩阵的行、列可能不是特别好理解，举个例子，在样例一中。

7 & 0 & 1\\ 8 & 3 & 2\\ 5 & 6 & 4 \end{Bmatrix} 2 & 1 &0\\ 4 & 7 & 8\\ 6 & 5 & 3 \end{Bmatrix}

这个具体如何实现呢？其实只需要正常按照 n 来枚举，用到判断特定元素时再 \times n 即可，具体可以见代码。

回到搜索本身，我们先按枚举行，再在行确定的情况下枚举列，那么 dfs 的结束条件就是当 x=n+1 时。这时，我们只需要判断当前矩阵是否为合法矩阵并记录答案即可。

那么这引入了一个问题，如何记录答案。STL 中有这样一个容器 pair，大概可以理解为一个类似结构体的东西，只不过结构体里面只有两个元素。这个刚好就可以用来解决这个问题，pair 当中的两个元素分别用于计算这个矩阵的行和列。

但是单用 pair 肯定是不够的，因为一个 pair 显然没办法记录整个答案。那么我们考虑再加一个容器，想到搜索实际上是用栈来实现的，所以可以考虑用栈。数组也是可以的，但是记录答案的大小，也就是代价不如栈方便，数组还要单独开一个变量记录大小并且实时更新而栈直接压进去就好了。 再次回到搜索，我们考虑枚举一个小矩阵转 i 次 90\degree 来算代价。每次递归到后面那个小矩阵即可，具体地，把 y 加上 1，s 加上 i 。之后我们在将当前这个矩形旋转 90\degree 。这时候有个问题，为什么是先往下搜索再旋转呢？因为当前这个矩形可能可以不用旋转。那么为什么旋转过后不用再搜一次呢？因为这个改过之后当前的这个矩阵会继承到下一次搜索的状态去，就默认改了。然后再记录一下答案。当我们枚举结束了过后就意味着当前这种情况枚举完了，清空临时记录答案的栈，准备下一种情况。

接下来怎么搜索解决了，问题还有两个，第一个是如何判断合法，第二个是如何旋转。

首先判断合法是容易的，根据题目要求，只需判断这个矩阵里有没有重复的数字即可。为什么不用判断缺少的数字？因为有重复数字代表着有缺少的数字。

如何旋转是类似于一个坐标变换的东西，在题解刚开始的时候提到过获取小矩阵内每一个元素的位置只需要将其 \times n 。那么整体枚举这个小矩阵的每一个元素就是，(x-1)\times n+1 \le x \le n\times x 且 (y-1)\times n+1 \le x \le n\times y ，这个不懂得可以手动模拟一下位置。这里有一个重点就是要取模于 n ，可以理解为这是一个类似循环节的东西，如果不模 n 的话就是一个 1\times n^2 的矩阵了。

至此，这道题就被解决了。有一个小优化，因为每行之间是独立的，所以如果上一个矩阵改完是不合法的，那么就直接返回。

细节还是很多的，大家可以参考一下。

#include<bits/stdc++.h>
using namespace std;
const int N=100;
char c;
int a[N][N];
int vis[N];
int tmp1[N][N];
int tmp2[N][N];
int ans=0x3f3f3f3f;
int n;
stack<pair<int,int> > an,da;
void change(int x,int y)//反转第 i 行，第 j 列的矩阵
{
    memset(tmp1,0,sizeof(tmp1));
    memset(tmp2,0,sizeof(tmp2));
    for(int i=(x-1)*n+1;i<=n*x;i++)
    {
        for(int j=(y-1)*n+1;j<=n*y;j++)
        {
            tmp1[(i-1)%n+1][(j-1)%n+1]=a[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
            for(int j=1;j<=n;j++)
            {
                tmp2[n+1-j][i]=tmp1[i][j];
            }

    }

    for(int i=(x-1)*n+1;i<=n*x;i++)
    {
        for(int j=(y-1)*n+1;j<=n*y;j++)
        {
            a[i][j]=tmp2[(i-1)%n+1][(j-1)%n+1];
        }

    }

}
bool check(int x,int y) //判断第 i 行，第 j 列的矩阵是否合法
{
    for(int i=1;i<=n*x;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n*y;j++)
        {
            if(vis[a[i][j]]) return 0;
            vis[a[i][j]]=1;
        }
    }
    for(int j=1;j<=n*y;j++)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n*x;i++)
        {
            if(vis[a[i][j]]) return 0;
            vis[a[i][j]]=1;
        }
    }
    return 1;
}
void dfs(int x,int y,int cnt)   //搜索
{
//  cout<<x<<" "<<y<<" "<<cnt<<endl;
    if(x==n+1)//结束条件
    {
//      cout<<check(n,n)<<endl;
        if(check(n,n))
        {
//          cout<<1<<endl;
            if(cnt<ans)//如果当前的代价小于答案的话更新
            {
                ans=cnt;
                da=an;
            }
        }
        return ;
    }
    if(check(x,y-1)==0) return ;
    if(y==n+1) dfs(x+1,1,cnt);
    for(int i=0;i<4;i++)
    {
        dfs(x,y+1,cnt+i);
        change(x,y);
        an.push(make_pair(x,y));
    }
    for(int i=0;i<4;++i)    an.pop();
}
int main()
{
    cin>>n;
    for(int i=1;i<=n*n;i++)
    {
        for(int j=1;j<=n*n;j++)
        {
            cin>>c;
            if(c>='0' and c<='9') a[i][j]=c-'0';
            else a[i][j]=c-'A'+10;//进制转换
        }
    }
    dfs(1,1,0);
    int sz=0;
    if(ans==0x3f3f3f3f) cout<<"-1\n";
    else
    {
        cout<<ans<<endl;
        pair<int,int>AA[N];//输出答案
        while(da.size())
        {
            AA[++sz]=da.top();
            da.pop();
        }
        for(int i=sz;i;i--) cout<<AA[i].first<<" "<<AA[i].second<<endl;
    }
    return 0;
}