又是一道dfs的题目。开始分析题目发现是一道求Graph通路的问题，开始思考用邻接表或矩阵建图，然后通路判断+遍历；后来看分析发现忽略了“字典序排列”，所以需要从A1开始按一定顺序搜索，而且采用dfs算法。代码如下：
#include<iostream> #include<string> #include<iomanip> #include<cstdlib> #include<string.h> #include<queue> #include<stack> #include<algorithm> #include<malloc.h> using namespace std; int add[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}}; int p,q; int visit[27][27]={0}; int n; struct Excl { int con; int len; }; stack<Excl> lst; int dfs(int i,int j,int b) { int m=0,sum=0; Excl md; visit[i][j]=1; md.len=i;md.con=j; lst.push(md); if(b==p*q) return b; else { if((i+add[0][0])>=0&&(i+add[0][0])<q&&(j+add[0][1])>=0&&(j+add[0][1])<p) { if(!visit[i+add[0][0]][j+add[0][1]]) sum=dfs(i+add[0][0],j+add[0][1],b+1); if(sum==p*q) return sum; } if((i+add[1][0])>=0&&(i+add[1][0])<q&&(j+add[1][1])>=0&&(j+add[1][1])<p) { if(!visit[i+add[1][0]][j+add[1][1]]) sum=dfs(i+add[1][0],j+add[1][1],b+1); if(sum==p*q) return sum; } if((i+add[2][0])>=0&&(i+add[2][0])<q&&(j+add[2][1])>=0&&(j+add[2][1])<p) { if(!visit[i+add[2][0]][j+add[2][1]]) sum=dfs(i+add[2][0],j+add[2][1],b+1); if(sum==p*q) return sum; } if((i+add[3][0])>=0&&(i+add[3][0])<q&&(j+add[3][1])>=0&&(j+add[3][1])<p) { if(!visit[i+add[3][0]][j+add[3][1]]) sum=dfs(i+add[3][0],j+add[3][1],b+1); if(sum==p*q) return sum; } if((i+add[4][0])>=0&&(i+add[4][0])<q&&(j+add[4][1])>=0&&(j+add[4][1])<p) { if(!visit[i+add[4][0]][j+add[4][1]]) sum=dfs(i+add[4][0],j+add[4][1],b+1); if(sum==p*q) return sum; } if((i+add[5][0])>=0&&(i+add[5][0])<q&&(j+add[5][1])>=0&&(j+add[5][1])<p) { if(!visit[i+add[5][0]][j+add[5][1]]) sum=dfs(i+add[5][0],j+add[5][1],b+1); if(sum==p*q) return sum; } if((i+add[6][0])>=0&&(i+add[6][0])<q&&(j+add[6][1])>=0&&(j+add[6][1])<p) { if(!visit[i+add[6][0]][j+add[6][1]]) sum=dfs(i+add[6][0],j+add[6][1],b+1); if(sum==p*q) return sum; } if((i+add[7][0])>=0&&(i+add[7][0])<q&&(j+add[7][1])>=0&&(j+add[7][1])<p) { if(!visit[i+add[7][0]][j+add[7][1]]) sum=dfs(i+add[7][0],j+add[7][1],b+1); if(sum==p*q) return sum; } visit[i][j]=0; lst.pop(); } return b; /*while(m<8) 这种算法有错误 { if((i+add[m][0])>=0&&(i+add[m][0])<q&&(j+add[m][1])>=0&&(j+add[m][1])<p) { if(!visit[i+add[m][0]][j+add[m][1]]) { Excl md;md.len=i+add[m][0];md.con=j+add[m][1]; lst.push(md); visit[i+add[m][0]][j+add[m][1]]=1; sum++; dfs(i+add[m][0],j+add[m][1],b+1); if(b!=p*q) { sum--; visit[i+add[m][0]][j+add[m][1]]=0;lst.pop(); } } } if(b==p*q) return 1; else if(m==7&&sum==0) { lst.pop(); visit[i][j]=0; return 0; } m++; } visit[i][j]=0; return 0;*/ } int main() { int i,j,pre=0; Excl md; stack <Excl> fin; cin>>n; while(pre<n) { cin>>q>>p; memset(visit,0,sizeof(visit)); dfs(0,0,1); for(i=0;i<q;i++) for(j=0;j<p;j++) { if(!visit[i][j]) { cout<<"Scenario #"<<pre+1<<":"<<endl<<"impossible\n\n"; while(lst.size()) lst.pop(); goto L1; } } cout<<"Scenario #"<<pre+1<<":"<<endl; while(lst.size()) { md=lst.top(); fin.push(md); lst.pop(); } while(fin.size()) { md=fin.top(); fin.pop(); printf("%c%d",'A'+md.con,md.len+1); } cout<<endl<<endl; L1: pre++; } return 0; }
