F. Bouncy Ball
给定\(n×m\)矩形，起点\(st\)，终点\(ed\)，有一小球从起点出发，每次可以选择4个方向，如果碰到边界就反弹，询问最后能否到达终点
题解：\(DFS\) + \(map\)记录状态
按照题意\(dfs\)模拟分类讨论即可，但是我们这边说一下什么情况下不会到达终点，也就是我们到达了以前被遍历过的状态，注意这边的状态包括了坐标和方向，所以我们可以用\(map\)记录状态是否被遍历
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e4 + 10, M = 4e5 + 10;
int n, m, sx, sy, ex, ey;
string dir;
int ans; // dir 1: 1 1 , 2:1 -1 ,3:-1 +1,4:-1 -1
bool flag;
bool f;
map<array<int, 3>, int> mp;
int cnt;
void dfs(int dir, int x, int y)
{
if (flag)
return;
if (f == false)
return;
if (x == ex && y == ey)
{
flag = true;
return;
}
if (mp[{x, y, dir}])
{
f = false;
return;
}
mp[{x, y, dir}]++;
if (dir == 1)
{
int nx = x + 1, ny = y + 1;
if (nx <= n && ny <= m)
dfs(1, nx, ny);
else if (nx > n && ny <= m)
{
ans++;
dfs(3, x - 1, ny);
}
else if (nx <= n && ny > m)
{
ans++;
dfs(2, nx, y - 1);
}
else
{
ans++;
dfs(4, x - 1, y - 1);
}
}
else if (dir == 2)
{
int nx = x + 1, ny = y - 1;
if (nx <= n && ny >= 1)
dfs(2, nx, ny);
else if (nx > n && ny >= 1)
{
ans++;
dfs(4, x - 1, ny);
}
else if (nx <= n && ny < 1)
{
ans++;
dfs(1, nx, y + 1);
}
else
{
ans++;
dfs(3, x - 1, y + 1);
}
}
else if (dir == 3)
{
int nx = x - 1, ny = y + 1;
if (nx >= 1 && ny <= m)
dfs(3, nx, ny);
else if (nx < 1 && ny <= m)
{
ans++;
dfs(1, x + 1, ny);
}
else if (nx >= 1 && ny > m)
{
ans++;
dfs(4, nx, y - 1);
}
else
{
ans++;
dfs(2, x + 1, y - 1);
}
}
else if (dir == 4)
{
int nx = x - 1, ny = y - 1;
if (nx >= 1 && ny >= 1)
dfs(4, nx, ny);
else if (nx < 1 && ny >= 1)
{
ans++;
dfs(2, x + 1, ny);
}
else if (nx >= 1 && ny < 1)
{
ans++;
dfs(3, nx, y + 1);
}
else
{
ans++;
dfs(1, x + 1, y + 1);
}
}
}
void solve()
{
ans = 0;
cnt = 0;
flag = false;
f = true;
cin >> n >> m >> sx >> sy >> ex >> ey;
cin >> dir;
mp.clear();
if (dir == "DL")
dfs(2, sx, sy);
else if (dir == "DR")
dfs(1, sx, sy);
else if (dir == "UR")
dfs(3, sx, sy);
else
dfs(4, sx, sy);
if (flag == true)
cout << ans << endl;
else
cout << -1 << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}