P1074 （C++代码）

解题思路:





注意事项:





参考代码:

暴力bfs:

#include <iostream>  
#include <stdio.h>  
#include <queue>  
#include <string.h>  
using namespace std;  
   
typedef struct  
{  
    int x, y;  
    int step;  
}Point;  
   
int m ,n;  
char map[150][150];  
int mark[150][150];  
Point sta, e, cur, ne;  
int dir[8][2] = {{-1,-2},{1,-2},{-1,2},{1,2},{-2,-1},{2,-1},{-2,1},{2,1}};//8个方向  
queue<Point>q;  
   
int bfs();  
   
int main()  
{  
    int i, j, step;  
    scanf("%d%d",&m,&n);  
    getchar();//此处getchar()不可省，否则坑爹  
  
    for(i=0; i<n; i++)  
    {  
        scanf("%s",map[i]);  
        for(j=0; j<m; j++)  
        {  
            if(map[i][j] == 'K')  
            {  
                sta.x = i;  
                sta.y = j;  
            }  
            if(map[i][j] == 'H')  
            {  
                e.x = i;  
                e.y = j;  
            }  
        }  
    }  
    step = bfs();  
  
    printf("%d\n",step);  
    return 0;  
}  
   
int bfs()  
{  
    int i;  
    while(!q.empty())//初始化队列  
        q.pop();  
    sta.step = 0;  
    mark[sta.x][sta.y] = 1;  
    q.push(sta);  
   
    while(!q.empty())  
    {  
        cur = q.front();  
        q.pop();  
   
        if(cur.x == e.x && cur.y == e.y)  
            return cur.step;  
        for(i=0; i<8; i++)  
        {  
            ne.x = cur.x + dir[i][0];  
            ne.y = cur.y + dir[i][1];  
            ne.step = cur.step + 1;  
            if(ne.x >= 0 && ne.x < n && ne.y >= 0 && ne.y < m &&   
                map[ne.x][ne.y] != '*' && mark[ne.x][ne.y] == 0)  
            {  
                q.push(ne);  
                mark[ne.x][ne.y] = 1;  
            }  
        }  
    }  
}