UVA 439 Knight Moves

 

// 题意:输入标准国际象棋棋盘上的两个格子,求马最少需要多少步从起点跳到终点

BFS求最短路:

bfs并维护距离状态cnt, vis记录是否访问过

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int r1, c1, r2, c2;
const int N=8;
int vis[N][N]; const int dr[] = {-2,-2,-1,-1, 1,1, 2,2};
const int dc[] = {-1, 1,-2, 2,-2,2,-1,1}; struct State {
int r, c;
int cnt;
State(int r=0, int c=0, int cnt=0):r(r),c(c),cnt(cnt) {}
bool operator == (const State& rhs)
{
return r==rhs.r && c==rhs.c;
}
}; void tr(char* p, int &r, int &c)
{
r=p[0]-'a';
c=p[1]-'1';
} int bfs()
{
State f(r1, c1, 0), t(r2, c2);
if(f==t) return 0; queue<State> Q;
Q.push(f);
vis[r1][c1]=1; while(!Q.empty())
{
State s=Q.front(); Q.pop();
if(s==t)
return s.cnt;
for(int i=0;i<8;i++)
{
int nr, nc;
nr=s.r+dr[i];
nc=s.c+dc[i];
if(nr>=0 && nr<8 && nc>=0 && nc<8 && !vis[nr][nc])
{
Q.push(State(nr, nc, s.cnt+1));
vis[nr][nc]=1;
}
}
}
return -1;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("./uva439.in" , "r", stdin);
#endif char p1[3];
char p2[3];
while(scanf("%s%s", p1, p2)!=EOF)
{
tr(p1, r1, c1);
tr(p2, r2, c2);
memset(vis, 0, sizeof vis);
int cnt=bfs();
printf("To get from %s to %s takes %d knight moves.\n", p1, p2, cnt); } return 0;
}

 

lrj代码:

vis记录是否访问过, d记录各个格子的距离(这个要学习)

// UVa439 Knight Moves
// Rujia Liu
// 题意:输入标准国际象棋棋盘上的两个格子,求马最少需要多少步从起点跳到终点
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; struct State {
int r, c;
State(int r, int c):r(r),c(c) {}
}; const int dr[] = {-2,-2,-1,-1, 1,1, 2,2};
const int dc[] = {-1, 1,-2, 2,-2,2,-1,1};
int d[8][8], vis[8][8]; int bfs(int r1, int c1, int r2, int c2) {
if(r1 == r2 && c1 == c2) return 0;
queue<State> Q;
d[r1][c1] = 0;
vis[r1][c1] = 1;
Q.push(State(r1, c1));
while(!Q.empty()) {
State s = Q.front(); Q.pop();
for(int i = 0; i < 8; i++) {
int newr = s.r + dr[i];
int newc = s.c + dc[i];
if(newr >= 0 && newr < 8 && newc >= 0 && newc < 8 && !vis[newr][newc]) {
Q.push(State(newr, newc));
vis[newr][newc] = 1;
d[newr][newc] = d[s.r][s.c] + 1;
if(newr == r2 && newc == c2) return d[newr][newc];
}
}
}
return -1;
} int main() {
char s[9], t[9];
while(scanf("%s%s", s, t) == 2) {
memset(vis, 0, sizeof(vis));
int ans = bfs(s[0]-'a', s[1]-'1', t[0]-'a', t[1]-'1');
printf("To get from %s to %s takes %d knight moves.\n", s, t, ans);
}
return 0;
}
上一篇:Hadoop分布式配置


下一篇:Windows下配置Nginx