codeforces_1065_D.three pieces

题意：一个正方形棋盘，三种棋子，knight：像中国象棋中的马一样走；bishop：斜着走；rook：中国象棋中的车。棋盘中每个格子中标着1--n*n的互不相同的数字，从1开始任选一种棋子开始走，在每个格子，要么移动棋子，要么更换一种棋子，每个格子可以重复走，移动或更换都算作一步。问从1按增序走到n*n，至少需要多少步，相同步数情况下选择替换次数最少的方案。

思路：这道题的难点在于每一步可以更换棋子，算上棋子种类，一共3维[i][j][p]，每走一步是从[i][j][p]走到[i'][j'][p']，在这种情况下问题有点复杂。但是可以发现任何一点到另一点最多可以3步走到，bishop和rook这两种非常容易算出步数，然后再通过dfs搜索一下knight需要的步数，每走一步验证三种情况，感觉应该可以，改天试试。实现时发现一个问题，可以先走一步再替换一次，再走一步，这样也是3步，这种情况不好处理。

另一种思路，官方题解的思路。为了化简问题，将[i][j][k]当做一种状态，用i*n*3+j*3+k映射为一个整数，由此可以构建状态的邻接矩阵，再使用最短路算法求出每个状态之间的最短路，最后按顺序dp一下。这个方法比较巧妙，将3维的状态映射到1维上，值得思考。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define LL long long

#define N 12

int n;

int getState(int x,int y,int p)

{

    return x*n*+y*+p;

}

struct Pair

{

    int mov,rep;

    Pair() {}

    Pair(int m,int r)

    {

        mov=m;

        rep=r;

    }

    bool operator < (const Pair t)const

    {

        if(mov+rep==t.mov+t.rep)

            return rep<t.rep;

        else

            return mov+rep<t.mov+t.rep;

    }

    Pair operator + (const Pair t)const

    {

        Pair ret;

        ret.mov=mov+t.mov;

        ret.rep=rep+t.rep;

        return ret;

    }

    int sum()

    {

        return mov+rep;

    }

};

int dx[]= {-,-,-,,,,,-}; //knight

int dy[]= {-,,,,,-,-,-};

Pair gra[N*N*][N*N*];

void buildGra()

{

    for(int i=; i<n*n*; i++)

        for(int j=; j<n*n*; j++)

            gra[i][j]=Pair(,);

    for(int i=; i<n; i++)

    {

        for(int j=; j<n; j++)

        {

            for(int k=; k<; k++)

                for(int l=; l<; l++)

                {

                    int t1=getState(i,j,k);

                    int t2=getState(i,j,l);

                    //cout<<"*"<<t1<<" "<<t2<<endl;

                    if(t1==t2)

                        gra[t1][t1]=Pair(,);

                    else

                        gra[t1][t2]=gra[t2][t1]=Pair(,);

                }

            for(int k=; k<; k++) //knight

            {

                int xx=i+dx[k];

                int yy=j+dy[k];

                if(xx>=&&xx<n&&yy>=&&yy<n)

                {

                    int t1=getState(i,j,);

                    int t2=getState(xx,yy,);

                    gra[t1][t2]=gra[t2][t1]=Pair(,);

                }

            }

            for(int k=-; k<=; k++) //bishop

                for(int l=-; l<=; l++)

                {

                    if(k==||l==)

                        continue;

                    int xx=i+k;

                    int yy=j+l;

                    while(xx>=&&xx<n&&yy>=&&yy<n)

                    {

                        int t1=getState(i,j,);

                        int t2=getState(xx,yy,);

                        gra[t1][t2]=gra[t2][t1]=Pair(,);

                        xx+=k;

                        yy+=l;

                    }

                }

            for(int k=i+; k<n; k++) //rook

            {

                int t1=getState(i,j,);

                int t2=getState(k,j,);

                gra[t1][t2]=gra[t2][t1]=Pair(,);

            }

            for(int k=j+; k<n; k++)

            {

                int t1=getState(i,j,);

                int t2=getState(i,k,);

                gra[t1][t2]=gra[t2][t1]=Pair(,);

            }

        }

    }

}

int main()

{

    int R[],C[];

    scanf("%d",&n);

    for(int i=; i<n; i++)

        for(int j=; j<n; j++)

        {

            int num;

            scanf("%d",&num);

            R[num]=i;

            C[num]=j;

        }

    buildGra();

    for(int k=; k<n*n*; k++)

        for(int i=; i<n*n*; i++)

            for(int j=; j<n*n*; j++)

                if(gra[i][k]+gra[k][j]<gra[i][j])

                    gra[i][j]=gra[i][k]+gra[k][j];

    Pair dp[N*N][];

    dp[][]=dp[][]=dp[][]=Pair(,);

    for(int i=; i<=n*n; i++)

    {

        dp[i][]=dp[i][]=dp[i][]=Pair(,);

        int xx=R[i],yy=C[i];

        for(int j=; j<; j++)

        {

            for(int k=; k<; k++)

            {

                int snow=getState(xx,yy,j);

                int slst=getState(R[i-],C[i-],k);

                if(dp[i-][k]+gra[slst][snow]<dp[i][j])

                    dp[i][j]=dp[i-][k]+gra[slst][snow];

            }

        }

    }

    Pair res(,);

    for(int i=; i<; i++)

        if(dp[n*n][i]<res)

            res=dp[n*n][i];

    printf("%d %d\n",res.sum(),res.rep);

    return ;

}

巴特西

codeforces_1065_D.three pieces_思维

最新文章

热门文章