题解：AT_abc400_d [ABC400D] Takahashi the Wall Breaker

XZDZD · 2025-04-06 08:49:08 · 题解

[ABC400D] Takahashi the Wall Breaker

题意分析

题目大意是简单的搜索，搜到墙时更新状态踢腿次数加一，搜完就可以了。但是这样搜会T，并且更新比较混乱。于是我们考虑优化。

优化

考虑开两条队列，第一条队列用来放次数为零也就是没有踢腿的点。第二条存踢过腿的点。优先处理第一条队列的点。这样就可以大大优化效率。

注意

对于练习搜索的初学者，需要注意 dis 要初始化一个大的值以便于更新，对于本题，由于踢腿范围是两格因此需要多写一种情况。

注意不要越界！！！

Code

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5 + 10;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct point
{
    int x,y,step;
};
int dis[1005][1005];
queue <point> q[2];
char mmap[1005][1005];
int h,w;
int sx,sy,ex,ey;
int main() {
    cin>>h>>w;
    for(int i = 1;i <= h; ++i){
        for(int j = 1;j <= w; ++j){
            cin>>mmap[i][j];
            if(mmap[i][j] == '#'){
                dis[i][j] = 1e9;
            }
            else{
                dis[i][j] = 1e9;
            }
        }
    }
    cin>>sx>>sy>>ex>>ey;
    q[0].push({sx,sy,0});
    dis[sx][sy] = 0;
    int cur = 0,nxt = 1;
    while (!q[0].empty() || !q[1].empty() ) {
        while (!q[cur].empty())
        {
            point u = q[cur].front(), v;
            q[cur].pop();
            for (int i = 0;i < 4; ++i) {
                bool wall = false;
                for (int j = 1;j <= 2; ++j) {
                    v.x = u.x + dx[i] * j;
                    v.y = u.y + dy[i] * j;
                    if (v.x < 1 || v.x > h || v.y > w || v.y < 1) continue;
                    if (mmap[v.x][v.y] == '#'){
                        wall = true;
                    } 
                    int to;
                    if (wall) { //关键代码，判断入哪个队列
                        to = nxt;
                        v.step = u.step + 1;
                    }else {
                        to = cur;
                        v.step = u.step;
                    }
                    if (dis[v.x][v.y] <= v.step) continue;
                    q[to].push(v);
                    dis[v.x][v.y] = v.step;
                }
            }
        }
        swap(cur,nxt);
    }
    cout<<dis[ex][ey];
    return 0;
}