為了方便說明，我們只討論$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誤判成垃圾留言，小莫會盡快將其手動還原
注意：只有此網誌的成員可以留言。