牛客哈理工小乐乐下象棋（深度理解bfs好题）

题目链接：

本题做法较多，可dp（记忆化搜索，bfs(想做对需要深度理解bfs和路径条数问题)）

dp记忆化搜索没什么坑点，简单

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 typedef long long ll;
 7 const ll mod=1e9+7;
 8 ll f[205][205][205];
 9 ll X[8]={-1,-2,-1,-2,1,2,1,2};
10 ll Y[8]={2,1,-2,-1,-2,-1,2,1};
11 ll n,m,k;
12  
13 ll so(ll x,ll y,ll step)
14 {
15     if(f[x][y][step]!=-1) return f[x][y][step];
16     if(step==k)
17     {
18         if(x==1 && y==m) return f[x][y][step]=1;
19         return f[x][y][step]=0;
20     }
21      
22     ll ans=0;
23     for(ll i=0;i<8;i++)
24     {
25         ll nx=x+X[i];
26         ll ny=y+Y[i];
27         if(nx>=1&&nx<=n && ny>=1&&ny<=m)
28         {
29             ans=(ans+so(nx,ny,step+1))%mod;
30         }
31     }
32      
33     f[x][y][step]=ans;
34     return f[x][y][step];
35 }
36          
37  
38 int main()
39 {
40     ios::sync_with_stdio(false); cin.tie(0);
41      
42     while(cin>>n>>m>>k)
43     {
44         for(ll i=0;i<=n+1;i++)
45             for(ll j=0;j<=m+1;j++)
46                 for(ll p=0;p<=k+1;p++)
47                     f[i][j][p]=-1;
48                      
49         ll ans=so(n,1,0);
50          
51         cout<<ans<<endl;
52     }
53      
54     return 0;
55 }

bfs做法很坑，还需要标记数组！要防止重复入队！(k次的时候也会重复入队，即次数要加上，但不能重复入队会多加!)

（模拟3，3，4；到k=2和3时可以找到未标记的错误）

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 typedef long long ll;
 9 const ll mod=1e9+7;
10 ll X[8]={-1,-2,-1,-2,1,2,1,2};
11 ll Y[8]={2,1,-2,-1,-2,-1,2,1};
12 ll n,m,k;
13 ll f[205][205][205];
14 ll vis[205][205][205];
15 struct px
16 {
17     ll st;
18     ll x;
19     ll y;
20     px(){};
21     px(ll S,ll X,ll Y):st(S),x(X),y(Y){};
22 }p;
23 
24 void bfs()
25 {
26     f[0][n][1]=1;//vis[0][n][1]=1;
27     queue<px> que;
28     que.push(px(0,n,1));
29 
30     while(!que.empty())
31     {
32         p=que.front();
33         que.pop();
34         if(p.st==k) continue;
35         //if(p.st>k) continue;
36 
37         for(ll i=0;i<8;i++)
38         {
39             ll nx=p.x+X[i];
40             ll ny=p.y+Y[i];
41             //if(p.st>k) continue;
42 
43             if(nx>=1&&nx<=n && ny>=1&&ny<=m)
44             {
45                 f[p.st+1][nx][ny]=(f[p.st+1][nx][ny]+f[p.st][p.x][p.y])%mod;
46 
47                 if(vis[p.st+1][nx][ny]) continue;//这2行标记很重要,不然会重复+算错(k次的时候也会重复入队)
48                 vis[p.st+1][nx][ny]=1;           //即次数要加上,但不能重复入队(会多加)!
49                 que.push(px(p.st+1,nx,ny));
50             }
51         }
52     }
53 }
54 
55 int main()
56 {
57     ios::sync_with_stdio(false); cin.tie(0);
58 
59     while(cin>>n>>m>>k)
60     {
61         for(ll p=0;p<=k+1;p++)
62             for(ll i=0;i<=n+1;i++)
63                 for(ll j=0;j<=m+1;j++)
64                     { f[p][i][j]=0; vis[p][i][j]=0;}
65 
66         bfs();
67         
68         cout<<f[k][1][m]<<endl;
69     }
70 
71     return 0;
72 }

完。