输入一个棋盘 ( p × q )，从任意点开始，每次走日子格，求能走遍每个点的序列，以Sample中给出的样式按字典序输出，如果得不到这样的序列输出impossible
由于要按字典序输出，所以优先访问坐标较小的点，第一次得到的序列就是所求结果
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int const maxn = 30;
bool vis[maxn][maxn];
int p, q;
bool flag = false;
int const steps[8][2] = { { -1, -2 }, { 1, -2 }, { -2, -1 }, { 2, -1 }, { -2, 1 }, { 2, 1 }, { -1, 2 }, { 1, 2 } };
typedef struct node
{
int x;
int y;
}coordinate;
bool judge()
{
for( int i = 0; i < p; i++ )
for( int j = 0; j < q; j++ )
if( !vis[i][j] )
return false;
return true;
}
vector<coordinate> path;
void dfs( int x, int y )
{
if( flag )
return;
if( judge() && !flag ) {
printf( "A1" );
for( int i = 0; i < path.size(); i++ ){
printf( "%c", path[i].y + 65 );
printf( "%d", path[i].x + 1 );
}
puts("");
flag = true;
return;
}
for( int i = 0; i < 8; i++ ) {
int next_x = x + steps[i][0];
int next_y = y + steps[i][1];
if( next_x >= 0 && next_x < p && next_y >= 0 && next_y < q && !vis[next_x][next_y] ) {
coordinate tmp;
tmp.x = next_x;
tmp.y = next_y;
path.push_back( tmp );
vis[next_x][next_y] = 1;
dfs( next_x, next_y );
vis[next_x][next_y] = 0;
path.pop_back();
}
}
}
int main()
{
int n; scanf( "%d", &n );
for( int i = 0; i < n; i++ ) {
scanf( "%d%d", &p, &q );
flag = false;
printf( "Scenario #%d:\n", i + 1 );
memset( vis, 0, sizeof( vis ) );
path.clear();
vis[0][0] = 1;
dfs( 0, 0 );
if( !flag )
printf( "impossible\n" );
puts("");
}
return 0;
}
posted on 2016-08-31 10:16
Vontroy 阅读(148)
评论(0) 编辑 收藏 引用