搜索水蓝。
题目传送门
拿到这个题目，第一眼就看到一个小玩意在网格中走，这不一眼 dfs 暴搜吗？
直接开搜。
code
/*********************************************************** Author : dingziyang888* Website : https://www.luogu.com.cn/problem/* Created Time :* FileName :* Warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!* 1.MLE?* 2.array size enough?* 3.long long?* 4.overflow long long?* 5.multiple task cleaned?* 6.freopen?* 7.TLE?* *******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <stack>
#define I using
#define AK namespace
#define IOI std
#define A return
#define C 0
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
I AK IOI;using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxn = 2e2 + 5;int ans, n, m, vv;
char c;int dx[4] = {1, 0, -1, 0};// x轴偏移量
int dy[4] = {0, 1, 0, -1};// y轴偏移量
int vis[maxn][maxn], g[maxn][maxn];// vis 记录有没有走过，g 记录障碍物位置stack<pair<int, int> > q;// 放栈里void out(int xx, int yy) {int x = q.top().first, y = q.top().second;while (!q.empty() && x != xx || y != yy) q.pop(), vis[x][y] = 0, x = q.top().first, y = q.top().second;
}//出栈void dfs(int bx, int by, int sm, int dep) {int now = sm;for (int d = 0; d < 4; d++) {int x = bx + dx[d], y = by + dy[d];while (!g[x][y] && !vis[x][y] && x <= n && x > 0 && y <= n && y > 0) { // 是否为障碍物 && 有没有走过 && 有没有出网格q.push(make_pair(x, y));vis[x][y] = 1;now++;x = x + dx[d], y = y + dy[d];}x = x - dx[d], y = y - dy[d];if (x == bx && y == by)continue;ans = max(ans, now);// 更新 ansif (!vis[x + dx[d]][y + dy[d]])dfs(x, y, now, dep + 1);// 偏移量也没走过，直接搜now = sm;out(bx, by);}
}int main() {freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);cin >> n >> m;for (int i = 1; i <= m; i++)cin >> c >> vv, g[vv][c - 'A' + 1] = 1;q.push(make_pair(1, 1));//初始化vis[1][1] = 1;//初始化dfs(1, 1, 1, 1);cout << ans << endl;return 0;
}