POJ 2488騎士遊歴A Knight's Journey解題報告

この問題には3点注意すべき点がある.
1、问题の意味を明らかにして、pは行番号を指して、上から下まで顺次1,2,3...p;qは列番号を指し、左からA,B,C,D...、ディクショナリシーケンスの出力は、まず列でソートし、左側は前で、同じ列は行でソートし、行番号が小さいのは前です.
2、あるブロックに再帰的に遭遇した次のステップがジャンプできない場合、上位に戻る前にvisマトリクスの対応する位置をクリアします!また、開始位置はA 1であり、A 1が解けなければ他の状況を遍歴する必要はなく、impossibleを直接出力すればよい.
3、出力するときは、それぞれの状況の後に1行のスペースがあることを覚えておいてください....
コードは次のとおりです.

#include<iostream>
#include<stack>

using namespace std;

int vis[8][8];

struct loc{
	int x,y;
	loc(int a,int b){
		x=a;y=b;
	}
};
stack<loc> que;

void clear_que(){
	while(que.size()!=0){
		que.pop();
	}
}

bool is_full(int map[8][8],int p,int q){
	for (int i=0;i<p;i++){
		for (int j=0;j<q;j++){
			if (map[i][j]==0){
				return 0;
			}
		}
	}
	return 1;
}
/********************************/
//	x:the row number in vis[][];
//	y:the column number in vis[][];
/*********************************/
/*bool dfs(int x,int y,int p,int q){		
	if (x<0 || y<0 || x>=p || y>=q) return 0;	//out of the range
	else if (vis[x][y]==1)	return 0;
	else {
		vis[x][y]=1;
		loc location(x,y);
		que.push(location);			//       
		if (is_full(vis,p,q)) return 1; 
		if (dfs(x-1,y-2,p,q)) return 1;
		if (dfs(x+1,y-2,p,q)) return 1;
		if (dfs(x-2,y-1,p,q)) return 1;
		if (dfs(x+2,y-1,p,q)) return 1;
		if (dfs(x-2,y+1,p,q)) return 1;
		if (dfs(x+2,y+1,p,q)) return 1;
		if (dfs(x-1,y+2,p,q)) return 1;
		if (dfs(x+1,y+2,p,q)) return 1;
		que.pop();				//        ，          ，  
		vis[x][y]=0;				//    ，  ！
		return 0;
	}
}
int main(){
	int cases;
	cin>>cases;
	int count=0;
	while(cases--){
		count++;
		clear_que();
		memset(vis,0,sizeof(vis));
		int p,q;
		cin>>p>>q;
		cout<<"Scenario #"<<count<<":"<<endl;
		
		if (dfs(0,0,p,q)) {
			stack<loc> out;
			while(!que.empty()){			//      ，        
				out.push(que.top());
				que.pop();
				}
			while(!out.empty()){
				cout<<(char)('A'+out.top().y)<<out.top().x+1;
				out.pop();
				}
			cout<<endl;
		}		
		else {cout<<"impossible"<<endl;}
	}
	return 0;
}

提出してからタイムアウトしたと言って、どうせ状況も多くなくて、時計を打つしかなくて、全部で12種類の情況の下で同じ道があって、残りはすべてimpossibleです.

if(p==1 &&q ==1)
			cout<<"A1"<<endl;
		else if(p==3 && q==4)
			cout<<"A1C2A3B1D2B3C1A2C3D1B2D3"<<endl;
		else if(p==3 && q==7)
			cout<<"A1B3D2F1G3E2G1F3E1G2E3C2A3B1C3A2C1D3B2D1F2"<<endl;
		else if(p==3 && q==8)
			cout<<"A1B3C1A2C3D1B2D3E1G2E3C2A3B1D2F1H2F3G1E2G3H1F2H3"<<endl;
		else if(p==4 && q==3)
			cout<<"A1B3C1A2B4C2A3B1C3A4B2C4"<<endl;
		else if(p==4 && q==5)
			cout<<"A1B3C1A2B4D3E1C2D4E2C3A4B2D1E3C4A3B1D2E4"<<endl;
		else if(p==4 && q==6)
			cout<<"A1B3C1A2B4C2D4E2F4D3E1F3D2B1A3C4B2A4C3E4F2D1E3F1"<<endl;
		else if(p==5 && q==4)
			cout<<"A1B3A5C4D2B1A3B5D4C2B4A2C1D3C5A4B2D1C3D5"<<endl;
		else if(p==5 && q==5)
			cout<<"A1B3A5C4A3B1D2E4C5A4B2D1C3B5D4E2C1A2B4D5E3C2E1D3E5"<<endl;
		else if(p==6 && q==4)
			cout<<"A1B3A5C6D4B5D6C4D2B1A3C2B4A2C1D3B2D1C3D5B6A4C5A6"<<endl;
		else if(p==7 && q==3)
			cout<<"A1B3C1A2C3B1A3C2B4A6C7B5A7C6A5B7C5A4B2C4B6"<<endl;
		else if(p==7 && q==4)
			cout<<"A1B3A5B7D6B5A7C6D4C2A3B1D2C4B2A4B6D7C5A6C7D5B4D3C1A2C3D1"<<endl;
		else if(p==8 && q==3)
			cout<<"A1B3C1A2B4C2A3B1C3A4B2C4A5B7C5A6B8C6A7B5C7A8B6C8"<<endl;
		else
			cout<<"impossible"<<endl;

そして当時はACとかハハハ、200 K、16 MSでした.
牛が私に第1のプログラムがどのように直接ACを修正することができることを指摘することができることを望んで、タイムアウトしません.ここで先にお礼を言います!!