Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

超时求助。。。

Posted by nangua1995 at 2017-03-03 23:22:49 on Problem 2488
#include <iostream>
using namespace std;
#define size 100
int data[size][size]={0};//没走的格子是0,走完变成1
int p,q;
bool findpath=false;
int DX[8]={-2,-2,-1,-1,+1,+1,+2,+2};
int DY[8]={-1,+1,-2,+2,-2,+2,-1,+1};
int path[2][size]={};//存储路径
int step=1;
int num=1;
void print(){
	printf("A1");
	for(int i=1;i<step;i++){
	  //printf("%c",'A'+path[1][size]);
	 
	 printf("%c",path[0][i]+'A'-1);
	 printf("%d",path[1][i]);
	}
	printf("\n");
}
bool exist0(){
  bool ret =false;
  for(int i=1;i<=p;i++){
     for(int j=1;j<=q;j++)
	 {
		 if(data[j][i]==0) 
			 ret = true;
	 }
  }
  return ret;
}
void dfs(int x,int y)
{
	//if(x==q&&y==p){
	//	findpath = true;
	//	print();
	//	return;
	//}
	if(!exist0()&&x==q&&y==p){
	   findpath  = true;
	   print();
	    return;
	   
	}
	data[1][1] = 1;
	for(int i=0;i<=8;i++){
		int NX = x + DX[i];
		int NY = y + DY[i];
		if(NX<=q&&NY<=p&&NX>0&&NY>0&&data[NX][NY]==0){
			int tmp = data[NX][NY];
			data[NX][NY] = 1;
			path[0][step] = NX;
			path[1][step] = NY;
			step++;
			dfs(NX,NY);
			
			data[NX][NY] = tmp;
			step--;
			path[0][step] = 0;
			path[1][step] = 0;
			
		}
	}
}
int main(){
	int n;
	cin>>n;
	path[0][0]=1;//初始位置
	path[1][0]=1;
	data[1][1]=1;
	while(n--){
    
	 cin>>p;
	 cin>>q;
	 printf("Scenario #%d:\n",num);
	 num++;
	 dfs(1,1);

	 if(!findpath){
		 printf("impossible\n");}
	 findpath = false;
	 step = 1;
	 for(int i=1;i<size;i++)
		 for(int j=0;j<size;j++)
		 {
			 data[i][j] = 0;
		 }
	 for(int i=0;i<size;i++){
	  path[0][i] = 0;
	  path[1][i] = 0;
	 }
	 }
	
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator