LOJ P10028 Knight Moves 题解

每日一题 day66 打卡

我很震惊一本通居然还有这么善良的题目。

Analysis

只需要一个广搜的模板就好了，值得注意的是做每个子任务之前记得清空队列。

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #define int long long
 7 #define maxn 310
 8 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 9 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
10 using namespace std;
11 inline int read()
12 {
13     int x=0,f=1;
14     char c=getchar();
15     while(c<'0'||c>'9') {if(c=='-') x=-x; c=getchar();}
16     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
17     return f*x;
18 }
19 inline void write(int x)
20 {
21     if(x<0){putchar('-');x=-x;}
22     if(x>9)write(x/10);
23     putchar(x%10+'0');
24 }
25 int T;
26 int n;
27 int ex,ey; 
28 int book[maxn][maxn];
29 struct node
30 {
31     int x,y,step;
32 }x[maxn];
33 queue q;
34 int dx[9]={0,1,1,-1,-1,2,2,-2,-2};
35 int dy[9]={0,2,-2,2,-2,1,-1,1,-1};
36 signed main()
37 {
38     T=read();
39     while(T--)
40     {
41         while(!q.empty()) q.pop();
42         memset(book,0,sizeof(book));
43         n=read();
44         x[1].x=read();x[1].y=read();
45         x[1].step=0;
46         ex=read();ey=read();
47         book[x[1].x][x[1].y]=1;
48         if(x[1].x==ex&&x[1].y==ey) 
49         {
50             write(0);
51             putchar('\n');
52             continue;
53         }
54         q.push(x[1]);
55         while(!q.empty())
56         {
57             node now=q.front();
58             q.pop();
59             int nx=now.x,ny=now.y,ns=now.step;
60             if(nx==ex&&ny==ey) 
61             {
62                 write(ns);
63                 putchar('\n');
64                 break;
65             }
66             rep(i,1,8)
67             {
68                 int xx=nx+dx[i],yy=ny+dy[i];
69                 if(book[xx][yy]==1||xx<0||xx>=n||yy<0||yy>=n) continue;
70                 book[xx][yy]=1;
71                 node sub;
72                 sub.x=xx;sub.y=yy;sub.step=ns+1;
73                 q.push(sub);
74             }
75         } 
76     }
77     return 0;
78 }

如有失误请各位大佬斧正（反正我不认识斧正是什么意思）