UVa 439 - Knight Moves 검색 테마

439-Knight Moves
13381
56.27%
5157
93.21%
제목 링크:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=380
제목 유형: 검색
샘플 입력:

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.

분석:
이 문제 도 매우 고전적 인 검색 입문 문제 다.문 제 는 장기 에서 말의 시작 위 치 를 지정 하고 목표 위치 와 함께 말 이 최소한 의 걸음 으로 목표 위치 에 도착 하도록 요구 하 는 것 이다.가장 짧 은 걸음 수 를 구 하 는 사람 은 일반적으로 BFS 로 하 는 것 이 좋다.
걸음 수 를 구 할 때 작은 기술 이 있 습 니 다. vis 배열 을 열 고 0 으로 초기 화 한 다음 에 이것 은 걸 어 가 는 걸음 수 를 기록 하 는 것 이 아니 라 걸 어 가 는 걸음 수 를 표시 하 는 데 사 용 됩 니 다.구체 적 으로 코드 참조

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char start[3], end[3];
int dir[8][2] = {{-2,1},{-1,2},{1,2},{2,1},
                 {2,-1},{1,-2},{-1,-2},{-2,-1}};

int vis[10][10]; 
struct Node{int x, y; };
Node que[1000];


void bfs(){
    int front=0, rear=1;
    que[0].x=start[0]-'a', que[0].y=start[1]-'0'-1;
    vis[que[0].x][que[0].y] = 1;
    while(front<rear){
        Node t = que[front++];
 	//          ，    
        if(t.x==end[0]-'a' && t.y==end[1]-'0'-1){ 
            printf("To get from %s to %s takes %d knight moves.
", start,end,vis[t.x][t.y]-1);
            return ;
        }
        for(int i=0; i<8; ++i){
            int dx=t.x+dir[i][0], dy=t.y+dir[i][1];
            if(dx>=0 && dx<8 && dy>=0 && dy<8 && !vis[dx][dy]){
                vis[dx][dy] = vis[t.x][t.y]+1;  //     
                Node temp;
                temp.x=dx, temp.y=dy;
                que[rear++] = temp;
            }
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    while(~scanf("%s %s", start, end) && start[0]){
        memset(vis, 0, sizeof(vis));
        bfs();
    }
    return 0;
}