[AtCoder Beginner Contest 265]E - Warp（dp + set）

题目传送门：E - Warp (atcoder.jp)

题意 / Problem

在二维平面中，从原点(0, 0)出发，进行N次移动，每次移动可以选择3个方向，分别是从\((x, y)\)移动到\((x + A, y + B)、(x + C, y + D)、(x + E, y + F)\)，只在整数点上运动。

有M个障碍点是不能走的。问N次移动后一共可以有多少种运动轨迹。

思路 / Thought

首先考虑怎么快速的判断一个大范围的点是否是障碍点，可以通过set这个数据结构来存储障碍点，再通过set.count({x, y})来判断(x, y)是否是障碍点，插入和查询的复杂度都是O(logM)。

看一下数据范围，\(N \le 300\)，所以\(O(N ^ 3)\)的空间复杂度是可以接受的。

定义dp[t][i][j]表示一共走了t步，第一个方向i步，第二个方向j步，第三个方向可以算出来是\(k = t - i - j\)步，有了步数可以算出当前位置，然后再往三个方向拓展，判断是否可以走到，再将当前方案加到后面的点里面去。

\(dp[t + 1][i + (g == 0)][j + (g == 1)] = (dp[t + 1][i + (g == 0)][j + (g = 1)] + dp[t][i][j]) \% p\)

代码 / Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int maxn = 303, p = 998244353;
int dp[maxn][maxn][maxn];// dp[n][x][y]
set<pair<int, int> > del;//不能达到的点 


void solve()
{
	int N, M;cin >> N >> M;
	vector<pair<int, int> > dir;//direction方向
	for(int i = 0;i < 3; ++ i)
	{
		int x, y;cin >> x >> y;
		dir.push_back({x, y});
	} 
	while(M --)
	{
		int x, y;cin >> x >> y;
		del.insert({x, y});
	}
	dp[0][0][0] = 1;
	for(int t = 0;t <= N; ++ t)//一共走了t次 
		for(int i = 0;i <= t; ++ i)//第一个方向 
			for(int j = 0;i + j <= t; ++ j)//第二个方向 
			{
				int k = t - i - j;
				int x = dir[0].fi * i + dir[1].fi * j + dir[2].fi * k;
				int y = dir[0].se * i + dir[1].se * j + dir[2].se * k;
				for(int g = 0;g < 3; ++ g)//下一个方向 
				{
					int nx = x + dir[g].fi, ny = y + dir[g].se;
					if(!del.count({nx, ny}))
						dp[t + 1][i + (g == 0)][j + (g == 1)] = (dp[t + 1][i + (g == 0)][j + (g == 1)] + dp[t][i][j]) % p;
				}
			}
	int ans = 0;
	for(int i = 0;i <= N; ++ i)
		for(int j = 0;i + j <= N; ++ j)
			ans = (ans + dp[N][i][j]) % p;
	cout << ans << '\n'; 
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	while(_ --)solve();
	return 0;
}