题解：P10988 [蓝桥杯 2023 国 Python A] 走方格

liuyi0905 · 2024-08-30 17:20:28 · 题解

广搜模版。

每一次可以向右或向下走一步，或者当 H_{x,y} 到 H_{x,y\pm L} 为一个严格递减序列时，可以走到 (x,y\pm L)，求 (1,1) 走到 (n,n) 的最短路。

队列里的元素表示可以走到的点，每次枚举队列里的点，按题意去模拟，将可以走到的点入队，并标记，标记过的点就不走。

记得队列要 pop。

代码：

void R(int x,int y,int w){
  if(x<1||x>n||y<1||y>n||f[x][y]){
    return;
  }
  f[x][y]=1;
  q.push({x,y,w});
}
int S(){
  for(R(1,1,0);q.size();q.pop()){
    auto [x,y,w]=q.front();
    if(x==n&&y==n){
      return w;
    }
    R(x+1,y,w+1);
    R(x,y+1,w+1);
    for(int i=y+1;i<=n&&a[x][i]<a[x][i-1];R(x,i++,w+1)){
    }
    for(int i=y-1;i>=1&&a[x][i]<a[x][i+1];R(x,i--,w+1)){
    }
  }
}