搜索专题: HDU1372Knight Moves
Knight Moves
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11832 Accepted Submission(s): 6969
the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
the row on the chessboard.
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
RunId : 21142000 Language : G++ Author : hnustwanghe
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 8+5;
int visit[N][N];
typedef struct node{
int x,y,step;
}Node;
const int dir[8][2]={{2,1},{-2,1},{-2,-1},{2,-1},{1,2},{1,-2},{-1,-2},{-1,2}};
int print(){
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++){
printf("%d",visit[i][j]);
if(j==7)
printf("\n");
}
}
int DBFS(int x,int y,int goalx,int goaly){
queue<Node> Q1,Q2;
Node t,s;
int step1=0,step2=0,flag =1,cnt,newx,newy,ans;
memset(visit,0,sizeof(visit));
t.x = x,t.y = y,t.step = 0;
s.x = goalx,s.y = goaly,s.step = 0;
visit[t.x][t.y] = 1;
visit[s.x][s.y] = 2;
Q1.push(t);
Q2.push(s);
while(flag){
cnt = Q1.size();
while(cnt--){
t = Q1.front();
if(t.x == goalx && t.y == goaly) return t.step;
for(int d=0;d<8;d++){
newx = t.x + dir[d][0];
newy = t.y + dir[d][1];
step1 = t.step + 1;
if(newx>0 && newx <= 8 && newy>0 && newy<=8){
if(visit[newx][newy]==2){
ans = step1 + step2;
return ans;
}
if(!visit[newx][newy]){
s.x = newx,s.y= newy,s.step = step1;
Q1.push(s);
visit[newx][newy] = 1;
}
}
}
Q1.pop();
}
cnt = Q2.size();
while(cnt--){
t = Q2.front();
if(t.x==x && t.y==y) return t.step;
for(int d=0;d<8;d++){
newx = t.x + dir[d][0];
newy = t.y + dir[d][1];
step2 = t.step + 1;
if(newx>0 && newx<=8 && newy>0 && newy <=8){
if(visit[newx][newy]==1){
ans = step1 + step2;
return ans;
}
if(!visit[newx][newy]){
s.x = newx,s.y = newy,s.step = step2;
Q2.push(s);
visit[newx][newy] = 2;
}
}
}
Q2.pop();
}
}
return -1;
}
void Input_and_solve(){
char ch[10];
int x,y,goalx,goaly;
while(gets(ch)!=NULL){
x = ch[0]-'a'+1;
y = ch[1]-'0';
goalx = ch[3]-'a'+1;
goaly = ch[4]-'0';
printf("To get from %c%c to %c%c takes %d knight moves.\n",ch[0],ch[1],ch[3],ch[4],DBFS(x,y,goalx,goaly));
//print();
}
}
int main(){
Input_and_solve();
}
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std; const int N = 8+5;
int visit[N][N];
typedef struct node{
int x,y,step;
}Node;
const int dir[8][2]={{2,1},{-2,1},{-2,-1},{2,-1},{1,2},{1,-2},{-1,-2},{-1,2}};
int print(){
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++){
printf("%d",visit[i][j]);
if(j==7)
printf("\n");
}
}
int DBFS(int x,int y,int goalx,int goaly){
queue<Node> Q1,Q2;
Node t,s;
int step1=0,step2=0,flag =1,cnt,newx,newy,ans;
memset(visit,0,sizeof(visit));
t.x = x,t.y = y,t.step = 0;
s.x = goalx,s.y = goaly,s.step = 0;
visit[t.x][t.y] = 1;
visit[s.x][s.y] = 2;
Q1.push(t);
Q2.push(s);
while(flag){
cnt = Q1.size();
while(cnt--){
t = Q1.front();
if(t.x == goalx && t.y == goaly) return t.step;
for(int d=0;d<8;d++){
newx = t.x + dir[d][0];
newy = t.y + dir[d][1];
step1 = t.step + 1;
if(newx>0 && newx <= 8 && newy>0 && newy<=8){
if(visit[newx][newy]==2){
ans = step1 + step2;
return ans;
}
if(!visit[newx][newy]){
s.x = newx,s.y= newy,s.step = step1;
Q1.push(s);
visit[newx][newy] = 1;
}
} }
Q1.pop();
}
cnt = Q2.size();
while(cnt--){
t = Q2.front();
if(t.x==x && t.y==y) return t.step;
for(int d=0;d<8;d++){
newx = t.x + dir[d][0];
newy = t.y + dir[d][1];
step2 = t.step + 1;
if(newx>0 && newx<=8 && newy>0 && newy <=8){
if(visit[newx][newy]==1){
ans = step1 + step2;
return ans;
}
if(!visit[newx][newy]){
s.x = newx,s.y = newy,s.step = step2;
Q2.push(s);
visit[newx][newy] = 2;
}
}
}
Q2.pop();
}
} return -1;
}
void Input_and_solve(){
char ch[10];
int x,y,goalx,goaly;
while(gets(ch)!=NULL){
x = ch[0]-'a'+1;
y = ch[1]-'0';
goalx = ch[3]-'a'+1;
goaly = ch[4]-'0';
printf("To get from %c%c to %c%c takes %d knight moves.\n",ch[0],ch[1],ch[3],ch[4],DBFS(x,y,goalx,goaly));
//print();
}
}
int main(){
Input_and_solve();
}
Problem : 1372 ( Knight Moves ) Judge Status : Accepted#include<iostream>
RunId : 21135178 Language : G++ Author : hnustwanghe
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std; typedef struct node{
int x,y,step;
}Node;
bool visit[10][10];
const int dir[8][2]={{-2,1},{-2,-1},{2,-1},{2,1},{1,2},{1,-2},{-1,2},{-1,-2}};
int BFS(int x,int y,int goalx,int goaly){
queue<Node>Q;
memset(visit,0,sizeof(visit));
int newx,newy;
Node t,s;
t.x = x,t.y = y,t.step = 0;
visit[t.x][t.y] = true;
Q.push(t); while(!Q.empty()){
t = Q.front();
if(t.x==goalx && t.y==goaly) return t.step;
for(int d=0;d<8;d++){
newx = t.x+dir[d][0];
newy = t.y+dir[d][1];
if(newx>=1 && newx<=8 && newy>=1 && newy<=8 && !visit[newx][newy]){
s.x = newx;
s.y = newy;
s.step = t.step+1;
Q.push(s);
}
}
Q.pop();
}
return -1;
}
void Input_data_and_solve(){
char a,c,ch[10];
int b,d,x,y,goalx,goaly;
while(gets(ch)!=NULL){
a = ch[0];
b = ch[1]-'0';
c = ch[3];
d = ch[4]-'0';
x = a-'a'+1;
y = b;
goalx = c-'a'+1;
goaly = d;
BFS(x,y,goalx,goaly);
printf("To get from %c%d to %c%d takes %d knight moves.\n",a,b,c,d,BFS(x,y,goalx,goaly));
}
}
int main(){
Input_data_and_solve();
}#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std; typedef struct node{
int x,y,step;
}Node;
bool visit[10][10];
const int dir[8][2]={{-2,1},{-2,-1},{2,-1},{2,1},{1,2},{1,-2},{-1,2},{-1,-2}};
int BFS(int x,int y,int goalx,int goaly){
queue<Node>Q;
memset(visit,0,sizeof(visit));
int newx,newy;
Node t,s;
t.x = x,t.y = y,t.step = 0;
visit[t.x][t.y] = true;
Q.push(t); while(!Q.empty()){
t = Q.front();
if(t.x==goalx && t.y==goaly) return t.step;
for(int d=0;d<8;d++){
newx = t.x+dir[d][0];
newy = t.y+dir[d][1];
if(newx>=1 && newx<=8 && newy>=1 && newy<=8 && !visit[newx][newy]){
s.x = newx;
s.y = newy;
s.step = t.step+1;
Q.push(s);
}
}
Q.pop();
}
return -1;
}
void Input_data_and_solve(){
char a,c,ch[10];
int b,d,x,y,goalx,goaly;
while(gets(ch)!=NULL){
a = ch[0];
b = ch[1]-'0';
c = ch[3];
d = ch[4]-'0';
x = a-'a'+1;
y = b;
goalx = c-'a'+1;
goaly = d;
BFS(x,y,goalx,goaly);
printf("To get from %c%d to %c%d takes %d knight moves.\n",a,b,c,d,BFS(x,y,goalx,goaly));
}
}
int main(){
Input_data_and_solve();
}
最新文章
- 【译】css动画里的steps()用法详解
- [GodLove]Wine93 Tarining Round #10
- C#之方法的重载与递归
- 『MySQL』索引类型 normal, unique, full text
- java.util.ConcurrentModificationException
- Oracle数据库 控制文件
- [RabbitMQ] AMQP close-reason, initiated by Library, code=541
- paip.log4j兼容linux windows 路径设置
- 设计js通用库
- 2014---多校训练2(ZCC Loves Codefires)
- O(V*n)的多重背包问题
- python之函数嵌套
- DAO设计模式 -- 使用数据库连接类连接MySql数据库并实现添加用户
- SGU 130
- JAXB - Annotations, Annotations for the Schema: XmlSchema
- ImportError: No module named pysqlite2 --安装pysqlite
- MIS框架开发计划
- 15第十五章UDF用户自定义函数(转载)
- sql中Statement与PreparedStatement的区别
- 导出文本pdf文件