$$\newcommand{\Ord}{\mathcal{O}}$$

1037. 水晶球 (Crystal Ball)

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

題目大意

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

題解

一個很暴力的$\Ord(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";
}