注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zjushuiping

追求的只是心中的那一份宁静!

 
 
 

日志

 
 

POJ2488  

2010-08-13 16:13:55|  分类: ACM/ICPC |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
A Knight's Journey
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 11297
Accepted: 3773

Description

POJ2488 - 地平线 - 超越地平线Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.

Sample Input

3
1 1
2 3
4 3

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

Source

TUD Programming Contest 2005, Darmstadt, Germany


#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
int map[10][10];

int move_q[8]={-2,-2,-1,-1,1,1,2,2};
int move_p[8]={-1,1,-2,2,-2,2,-1,1};
struct node{
       int x;
       int y;
       }grap[64];
      
       char s[200];
       int flag=0;
       int num;
      
int dfs(int p,int q,int fx,int fy)
{
    int i,j,k;
    int x,y;
   
   
    if(num==p*q)
    return 1;
    for(i=0;i<8;i++)
    {
                    x=fx+move_p[i];
                    y=fy+move_q[i];
                    if(x<1||y<1)
                    continue;
                    if(x>p||y>q)
                    continue;
                    if(map[x][y])
                    continue;
                    map[x][y]=1;
                    s[flag++]=(char)('A'+y-1);
                    s[flag++]=(char)('0'+x);
                    num++;
                    if(dfs(p,q,x,y))
                    return 1;
                    map[x][y]=0;
                    flag--;
                    flag--;
                    num--;
                   
    }
    return 0;
}
                   
   
   
 



int main(int argc, char *argv[])
{//freopen("C:/Users/shp/Desktop/in.txt","r",stdin);
 //freopen("C:/Users/shp/Desktop/out.txt","w",stdout);
 int n;
 cin>>n;
 int i,j,k;
 int p,q;
 for(k=1;k<=n;k++)
 {cin>>p>>q;
 
 flag=0;
  for(j=1;j<=q;j++)
  for(i=1;i<=p;i++)
  {num=0;
   flag=0;
   memset(map,0,sizeof(map));
  s[flag++]=(char)('A'+j-1);
  s[flag++]=(char)('0'+i);
  num=1;
  map[i][j]=1;
  
  if(dfs(p,q,i,j))
  {s[flag]='\0';cout<<"Scenario #"<<k<<":"<<endl;cout<<s<<endl<<endl;goto L;}
  //else
  //{cout<<"Scenario #"<<i<<":"<<endl;cout<<"impossible\n\n";  }  
 
 
 
   }  
  
  
 
  cout<<"Scenario #"<<k<<":"<<endl;cout<<"impossible\n\n";
  L:;
                 
                 
                 
                 
                 
                 
 }
 
 
                   

               
 
  
    system("PAUSE");
    return EXIT_SUCCESS;
}

  评论这张
 
阅读(602)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017