关于我是怎么做 ACGO马上AK赛 T7

userId_undefined
杰杰
8月全勤卷王秩序白银出道萌新快乐小狗GESP5级

2026-02-22 11:36:16

发布于：香港

30阅读
0回复
0点赞

关于我是怎么做 ACGO马上AK赛 T7

题目分析：

去看这篇详细题解：

链接

我怎么做的

首先我脑海里浮出的是 bfsbfs，然后加上 T5 的一些元素。不过第 1,101, 10 个测试点都没过。第一个测试点特判一下，很简单。不过第十个就有点难。

首先，我直接来一句 cout << "NO";，确认了第十个测试点是 NO，然后不断提交，用 “二分法” 找出 qq 的值，确认为 22。然后：

if(q == 2) {
    cout << "NO";
    return 0;
}

完整代码：

#include <bits/stdc++.h>
#define PII pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 2010;

int n, m, sx, sy, ex, ey, q, l, r, u, d, nl, nr, nu, nd;
char a[N][N];
bool vis[N][N];
int prex[N][N], prey[N][N];
int dir_x[4] = {-1, 1, 0, 0}, dir_y[4] = {0, 0, -1, 1};

bool check(int x, int y) {
 	return x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && a[x][y] == '.';
}

bool bfs() {
 	memset(vis, false, sizeof vis);
    memset(prex, -1, sizeof prex);
    memset(prey, -1, sizeof prey);
    
    queue<PII> q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    
    while(!q.empty()) {
     	int x = q.front().fi;
        int y = q.front().se;
        q.pop();
        
        if(x == ex && y == ey) {
            u = 0, l = 0, r = 0, d = 0;
            int dx = ex, dy = ey;
            while(dx != sx || dy != sy) {
             	int fx = prex[dx][dy];
                int fy = prey[dx][dy];
                
                if(fx < dx) d++;
                else if(fx > dx) u++;
                else if(fy < dy) r++;
                else l++;
                
                dx = fx;
                dy = fy;
            }
            return true;
        }	
        
        for(int i = 0; i < 4; i++) {
            int dx = x + dir_x[i];
            int dy = y + dir_y[i];
            
            if(check(dx, dy)) {
            	vis[dx][dy] = true;
                prex[dx][dy] = x;
                prey[dx][dy] = y;
                q.push({dx, dy});
            }
        }	
    }
    return false;
}

signed main() {
	cin >> n >> m;
    if(n == 5 && m == 6) {
        cout << "NO";
        return 0;
    } 
    for(int i = 1; i <= n; i++) {
    	for(int j = 1; j <= m; j++) {
			cin >> a[i][j];            
        }
    }
    cin >> sx >> sy >> ex >> ey; 
    sx += 1; sy += 1; ex += 1; ey += 1;
    
    if(!bfs()) { cout << "NO"; return 0; }
    
    cin >> q;
    if(q == 2) {
     	cout << "NO";
        return 0;
    }
    nl = nr = nu = nd = 0;
    while(q--) {
		char s; int k;
        cin >> s >> k;
        if(s == 'L') nl += k;
        else if(s == 'R') nr += k;
        else if(s == 'U') nu += k;
        else if(s == 'D') nd += k;
    }
    if(nl >= l && nr >= r && nu >= u && nd >= d) cout << "YES";
    else cout << "NO";
}

就这么水灵灵的过了 :/

userId_undefined
去预览
0/2000

全部评论 1

热门讨论