1.POJ2488 A Knight's Journey
search
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std; #define N 27
#define INF 0x7FFFFFFF
int p,q,_count=;
int _dec[N][N];
int routine[*N];
int t1,t2;
int flag,flag2; void path(int x,int y,int k)
{
switch (k)
{
case :{t1 = x-;t2 = y-;break;}
case :{t1 = x+;t2 = y-;break;}
case :{t1 = x-;t2 = y-;break;}
case :{t1 = x+;t2 = y-;break;}
case :{t1 = x-;t2 = y+;break;}
case :{t1 = x+;t2 = y+;break;}
case :{t1 = x-;t2 = y+;break;}
case :{t1 = x+;t2 = y+;break;}
}
}
void OUTPUT()
{
for (int i=;i<_count;i++)
{
cout<<(char)('A'+routine[*i+])<<routine[*i]+;
if (i==_count-) cout<<endl;
}
}
bool DFS(int x,int y)
{
if (flag2 == ) return ;
_dec[x][y]=;
routine[*_count]=x;
routine[*_count+]=y;
_count++;
if (_count>p*q)
{
flag2 = ;
return ;
}
if ((_count == p*q)&&(flag == ))
{
OUTPUT();
flag = ;
return ;
}
for (int k=;k<;k++)
{
path(x,y,k);
int xx=t1,yy = t2;
if ((xx>=)&&(xx<p)&&(yy>=)&&(yy<q)&&(_dec[xx][yy]==))
if (DFS(xx,yy)) return ;
}
_dec[x][y]=;
_count--;
return ;
}
int main()
{
int n;
cin>>n;
for (int m=;m<=n;m++)
{
for (int i=;i<N;i++)
for (int j=;j<N;j++)
_dec[i][j]=;
memset(routine,,sizeof(routine));
cin>>p>>q;
cout<<"Scenario #"<<m<<":"<<endl;
if ((p==)&&(q==))
{
cout<<"A1"<<endl<<endl;
continue;
}
if (p*q> || p>= || q>= || p<= || q<=)
{
cout<<"impossible"<<endl<<endl;
continue;
}
_count = ;
flag = ;
flag2 = ;
DFS(,);
if ((flag2 == )||(flag==)) cout<<"impossible"<<endl;
cout<<endl;
}
return ;
}
2.POJ 1077 Eight