hdu 1728

http://acm.hdu.edu.cn/showproblem.php?pid=1728

一道BFS搜索的水题，但是也弄了挺久的，有两个地方要注意一下

一是对于某个点，并不是说这个点走过了，就不能走了，而是这个点不添加到队列里去了，但是还是可以走的

二是一次走的方向，不止一个点，应该走一条直线

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <queue>
 4 #include <string.h>
 5 #define jud(Node) Node.x>=1&&Node.x<=m&&Node.y>=1&&Node.y<=n
 6 using namespace std;
 7 
 8 
 9 struct Node
10 {
11     int x,y;
12     int step;
13     int dic;
14 };
15 
16 int m,n,t;
17 int x1,x2,y1,y2,most;
18 char gra[105][105];
19 bool mark[105][105];
20 int dic[4][2] = {1,0,-1,0,0,1,0,-1};
21 
22 queue<Node>s;
23 
24 bool bfs()
25 {
26     Node tmp,tmp1;
27     tmp.x = y1;
28     tmp.y = x1;
29     tmp.step = -1;
30     tmp.dic = 5;
31     mark[tmp.x][tmp.y] = false;
32     while(!s.empty())
33         s.pop();
34     s.push(tmp);
35     while(!s.empty())
36     {
37         tmp = s.front();
38         s.pop();
39         if(tmp.x==y2&&tmp.y==x2&&tmp.step<=most)
40             return true;
41         for(int i = 0; i<4; i++)
42         {
43             tmp1.x = tmp.x + dic[i][0];
44             tmp1.y = tmp.y + dic[i][1];
45             while(gra[tmp1.x][tmp1.y]=='.'&&jud(tmp1))
46             {
47                 if(mark[tmp1.x][tmp1.y])
48                 {
49                     tmp1.step = tmp.step+1;
50                     mark[tmp1.x][tmp1.y] = false;
51                     s.push(tmp1);
52                 }
53                 Node tmp2;
54                 tmp2.x = tmp1.x+dic[i][0];
55                 tmp2.y = tmp1.y+dic[i][1];
56                 tmp1 = tmp2;
57             }
58         }
59     }
60     return false;
61 }
62 
63 int main()
64 {
65     scanf("%d",&t);
66     bool ans;
67     while(t--)
68     {
69         ans = false;
70         scanf("%d%d",&m,&n);
71         getchar();
72         memset(gra,0,sizeof(gra));
73         memset(mark,true,sizeof(mark));
74         for(int i = 1; i<=m; i++)
75             scanf("%s",gra[i]+1);
76         scanf("%d%d%d%d%d",&most,&x1,&y1,&x2,&y2);
77         ans = bfs();
78         if(ans)
79             printf("yes
");
80         else printf("no
");
81     }
82     return  0;
83 }