2016年2月12日 星期五

[Codeforces 472E]Design Tutorial: Learn from a Game

為了讓意義更加清楚,我用$R$取代了$N$,$C$取代了$M$
為了方便說明,我們只討論$R\geq C$的情況,如果$R<C$,將整個矩陣轉置即可

首先,數數看顏色數量有沒有一樣,如果有任何一個不一樣,輸出-1

如果一樣,我們可以從任何一顆顏色與$(R,C)$相同的珠子 (我們叫這棵被轉的珠子$P$好了) 開始轉,按照以下順序將對應的顏色轉到目標位置:

01 02 04 07 11
03 06 10 15 16
05 09 14 20 21
08 13 19 25 26
12 18 24 29 30
17 23 28 32 33
22 27 31 34 35

依照類似這樣的順序就可以保證在不影響目前排好的珠子的情況下,將新的珠子轉到對應的位置上了
除非$C=1$,這種情況就要特判,直接枚舉被移動的珠子的起點和終點即可

要將一顆珠子$G$從$A$點轉到$B$點時,可以考慮以下方法:
求出$A$點到$B$點的一條合法路徑$\{S_{1},S_{2},S_{3}, ...\}$
假設現在$G$在$S_{i}$點,可以考慮將$P$在不影響$G$的位置的情況下移動到$S_{i+1}$點 (我用了bfs搜索路徑),然後$P$再移動到$S_{i}$點,這樣$G$就跑到$S_{i+1}$點了
重複上述過程,直到$G$跑到$B$點為止

實作上需要求非常多次從$A$點到$B$點不經過一些點的路徑,寫成一個函數會比較方便 (code裡面的void GetPath(const int source,const int target,vector<int>&path))

還有諸多容易出錯的bug,詳情請參考code (?)

時間複雜度:$O((NM)^{2}(N+M))$ (因為進行了$NM(N+M)$次bfs,每次bfs的時間複雜度為$O(NM)$)

p.s. 若使用A*搜索路徑,效率還可以再提升一個等級,雖然理論時間複雜度不變,但在此題讓A*從$O((N+M)\log(NM))$退化成$O(NM\log(NM))$的最壞情況是不可能發生的
p.s. 偷偷告訴你,鑽礦遊戲Digging Game 2的AI經過改良後,也利用了A*算法搜索路徑,速度快了100倍!

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=2147483647;
int R,C,GRID[32][32],TARGET[32][32],CUR;
int VIS[32][32],KASE;
vector<int>ANS;
bool Valid()
{
    static int cnt[901];
    for(int i=1;i<=900;i++)cnt[i]=0;
    for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)cnt[GRID[i][j]]++;
    for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)cnt[TARGET[i][j]]--;
    for(int i=1;i<=900;i++)if(cnt[i]!=0)return false;
    return true;
}
int Point(const int r,const int c){return r*(C+2)+c;}
void Extract(const int loc,int &r,int &c){r=loc/(C+2),c=loc%(C+2);}
int Get(const int s[32][32],const int loc){static int r,c;Extract(loc,r,c);return s[r][c];}
int Select(const int color)
{
    for(int i=1;i<=R;i++)for(int j=C;j>=1;j--)if(VIS[i][j]<KASE&&Point(i,j)!=CUR&&GRID[i][j]==color)return Point(i,j);
    assert(0);return -1;
}
void MoveCUR(const int loc)
{
    static int r1,c1,r2,c2;
    Extract(CUR,r1,c1),Extract(loc,r2,c2);
//    printf("CUR:(%d,%d)=>(%d,%d)\n",r1,c1,r2,c2);
    assert(max(abs(r1-r2),abs(c1-c2))==1);
    swap(GRID[r1][c1],GRID[r2][c2]);
    ANS.push_back(loc),CUR=loc;
}
//void PrintLoc(const int loc){int r,c;Extract(loc,r,c),printf("(%d,%d)\n",r,c);}
void GetPath(const int source,const int target,vector<int>&path)
{
//    puts("source:"),PrintLoc(source),puts("target:"),PrintLoc(target);
    static int pre[32][32];
    queue<int>q;q.push(source),q.push(source);
    bool found=false;
    while(!q.empty())
    {
        static int r,c;
        Extract(q.front(),r,c),q.pop();
        const int pre_loc=q.front();q.pop();
        if(VIS[r][c]>=KASE)continue;
        assert(1<=r&&r<=R&&1<=c&&c<=C);
        VIS[r][c]=KASE;
        pre[r][c]=pre_loc;
        if(Point(r,c)==target){found=true;break;}
        static int d[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        for(int i=0;i<8;i++)q.push(Point(r+d[i][0],c+d[i][1])),q.push(Point(r,c));
    }
    assert(found);
    path.clear();
    for(int cur=target;cur!=source;cur=Get(pre,cur))path.push_back(cur);
    path.push_back(source);
    for(int l=0,r=(int)path.size()-1;l<r;l++,r--)swap(path[l],path[r]);
    KASE++;
}
void MoveCUR(const int target,const int banned)
{
    if(CUR==target)return;
    if(true){int r,c;Extract(banned,r,c);VIS[r][c]=KASE;}
    vector<int>path;
    GetPath(CUR,target,path);
    for(int i=1;i<(int)path.size();i++)MoveCUR(path[i]);
}
void MoveBeedOneStep(const int source,const int target)
{
    MoveCUR(target,source);
    MoveCUR(source);
}
void MoveBeed(const vector<int>&path)
{
    for(int i=1;i<(int)path.size();i++)MoveBeedOneStep(path[i-1],path[i]);
}
bool SameAsTARGET()
{
    for(int r=1;r<=R;r++)for(int c=1;c<=C;c++)if(GRID[r][c]!=TARGET[r][c])return false;
    return true;
}
bool Solve()
{
    assert(R>=C);
    if(!Valid())return false;
    ANS.clear();
    if(C==1)
    {
        static int grid_backup[32];
        for(int r=1;r<=R;r++)grid_backup[r]=GRID[r][1];
        for(int i=1;i<=R;i++)for(int j=1;j<=R;j++)if(i!=j)
        {
            ANS.clear(),ANS.push_back(CUR=Point(i,1));
            if(j<i)
            {
                for(int k=i-1;k>=j;k--)MoveCUR(Point(k,1));
            }
            else
            {
                for(int k=i+1;k<=j;k++)MoveCUR(Point(k,1));
            }
            if(SameAsTARGET())return true;
            for(int k=1;k<=R;k++)GRID[k][1]=grid_backup[k];
        }
        return false;
    }
    ANS.push_back(CUR=Select(TARGET[R][C]));
    for(int sum=2;sum<R+C;sum++)
    {
        vector<int>rs,cs;
        for(int r=1;r<sum&&r<=R;r++)
        {
            const int c=sum-r;
            if(c>C)continue;
            rs.push_back(r),cs.push_back(c);
        }
        for(int l=1,r=(int)rs.size()-1;l<r;l++,r--)swap(rs[l],rs[r]),swap(cs[l],cs[r]);
        for(int i=0;i<(int)rs.size();i++)
        {
            const int r=rs[i],c=cs[i];
            if(Point(r,c)!=CUR&&GRID[r][c]==TARGET[r][c])goto do_continue;
            static vector<int>path;
            GetPath(Select(TARGET[r][c]),Point(r,c),path);
            MoveBeed(path);
            do_continue:;
            assert(GRID[r][c]==TARGET[r][c]);
            VIS[r][c]=INF;
//            for(int i=1;i<=R;i++)
//            {
//                for(int j=1;j<=C;j++)printf("%d",GRID[i][j]);puts("");
//            }puts("");
        }
    }
    return true;
}
int main()
{
//    freopen("inn.txt","r",stdin);
    while(scanf("%d%d",&R,&C)==2)
    {
        for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)scanf("%d",&GRID[i][j]);
        for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)scanf("%d",&TARGET[i][j]);
        bool flipped=false;
        if(R<C)
        {
            const int n=max(R,C);
            for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)swap(GRID[i][j],GRID[j][i]),swap(TARGET[i][j],TARGET[j][i]);
            swap(R,C);
            flipped=true;
        }
        for(int i=0;i<=R+1;i++)for(int j=0;j<=C+1;j++)VIS[i][j]=0;
        for(int i=0;i<=R+1;i++)VIS[i][0]=VIS[i][C+1]=INF;
        for(int i=0;i<=C+1;i++)VIS[0][i]=VIS[R+1][i]=INF;
        KASE=1;
        if(Solve())
        {
            printf("%d\n",(int)ANS.size()-1);
            for(const int loc:ANS)
            {
                static int r,c;Extract(loc,r,c);
                if(flipped)swap(r,c);
                printf("%d %d\n",r,c);
            }
        }
        else puts("-1");
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原