經典搜索問題。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/6 7:47:26
* File Name: poj2488.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(27);
const int dx[]={-2,-2,-1,1,2,2,1,-1},dy[]={-1,1,2,2,1,-1,-2,-2};
int n,m;
string ans,d;
bool used[kMaxn][kMaxn];
string itoa(int x)
{
string re,t;
while(x>0)
{
t+=(x%10+'0');
x/=10;
}
for(int i=t.size()-1;i>=0;i--)
re+=t[i];
return re;
}
void erase(string &t)
{
int pos;
for(pos=t.size()-1;pos>=0;pos--)
if(isalpha(t[pos]))
break;
t.erase(pos,t.size()-pos);
}
void dfs(int depth,int x,int y)
{
if(ans<=d)
return;
if(depth>n*m)
{
ans=d;
return;
}
for(int i=0;i<8;i++)
{
int newx(x+dx[i]),newy(y+dy[i]);
if(newx<1 || newx>n || newy<1 || newy>m || used[newx][newy])
continue;
d+=(char)(newx+'A'-1);
d+=itoa(newy);
used[newx][newy]=true;
dfs(depth+1,newx,newy);
erase(d);
used[newx][newy]=false;
}
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
for(int case_num=1;case_num<=T;case_num++)
{
scanf("%d%d",&m,&n);
ans="z";
for(int i=1;i<=min(Half(n)+1,n);i++)
for(int j=1;j<=min(Half(m)+1,m);j++)
{
d+=(char)(i+'A'-1);
d+=itoa(j);
used[i][j]=true;
dfs(2,i,j);
erase(d);
used[i][j]=false;
}
printf("Scenario #%d:\n",case_num);
if(ans<"z")
cout<<ans<<endl;
else
cout<<"impossible"<<endl;
cout<<endl;
}
return 0;
}
posted on 2011-08-06 08:25
lee1r 閱讀(222)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索