TYVJ 1074 武士风度的牛(BFS)

 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 char a[151][151];
 8 int vis[151][151];
 9 int dir[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{-1,2},{2,1},{1,2}};
10 int ans,n,m;
11 struct node
12 {
13     int x,y;
14     int step;
15 }star;
16 void BFS()
17 {
18     memset(vis,0,sizeof(vis));
19     vis[star.x][star.y]=1;
20     ans=0;
21     queue<node> q;
22     q.push(star);
23     while(!q.empty())
24     {
25         node now;
26         now=q.front();
27         q.pop();
28         if(a[now.x][now.y]==‘H‘)
29         {
30             ans=now.step;
31             return ;
32         }
33         for(int i=0;i<8;i++)
34         {
35             node next;
36             next.x=now.x+dir[i][0];
37             next.y=now.y+dir[i][1];
38             next.step=now.step+1;
39             if(0<=next.x&&next.x<n&&0<=next.y&&next.y<m&&a[next.x][next.y]!=‘*‘&&!vis[next.x][next.y])
40             {
41                 vis[next.x][next.y]=1;
42                 q.push(next);
43             }
44         }
45     }
46 }
47 int main()
48 {
49     scanf("%d %d",&m,&n);
50     for(int i=0;i<n;i++)
51         scanf("%s",a[i]);
52     for(int i=0;i<n;i++)
53         for(int j=0;j<m;j++)
54         {
55             if(a[i][j]==‘K‘)
56             {
57                 star.x=i;
58                 star.y=j;
59                 star.step=0;
60             }
61         }
62     BFS();
63     printf("%d\n",ans);
64     return 0;
65 }