連結：https://tioj.ck.tp.edu.tw/problems/1037

題目大意

再二維 N×M 的格子中，有一個起點與終點，今天要從起點走 K 步，每步的距離為 di，方向上下左右任選，如果走超出格子就循環的走，問是否存在一種方法可以走到終點。

題解

一個很暴力的 O(KNM) 動態規劃，因為複雜度看起來很危險，但時間挺寬鬆的，所以對細節做了一些優化，然後就過了，而且還頗快的

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

bool dp[2][100][100];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N,M,T,d1,d2;
    int sx,sy,ex,ey;
    cin>>N>>M>>sx>>sy>>ex>>ey;
    cin>>T;

    dp[0][sx][sy]=1;

    #define add(x,y,n) ( x+y<n?x+y:x+y-n )
    #define del(x,y,n) ( x-y>=0?x-y:x-y+n )
    for(int k=1;k<=T;++k)
    {
        cin>>d1;
        d2=d1%M;
        d1%=N;
        for(int i=0;i<N;++i)
            for(int j=0;j<M;++j)
                dp[k&1][i][j] = dp[(k-1)&1][add(i,d1,N)][j] |
                                dp[(k-1)&1][del(i,d1,N)][j] | 
                                dp[(k-1)&1][i][add(j,d2,M)] | 
                                dp[(k-1)&1][i][del(j,d2,M)] ;
    }

    if(dp[T&1][ex][ey])cout<<"YES\n";
    else cout<<"NO\n";
}