CF1575J Jeopardy of Dropped Balls 题解

wdgm4 · 2022-10-20 10:49:49 · 题解

这道题其实真挺简单的，我才不会告诉你我调这道题的错要调傻了。

我是用搜索做的。

个人认为搜索算是一种优雅的暴力，较为简单的搜索只需按照题目的要求，去模拟一些题目要求的步骤，有时加一亿点剪枝，很容易就能 AC。

思路

按照题意，小球有三种移动方式，分别为向左，向右和向下。 而数组 a 控制着小球的移动方向。 此题唯一特殊的地方是小球经过的地方会改变 a_{ij} 的值。 我们只需用搜索维护小球的移动和 a_{ij} 的改变即可。

下面代码中的 dfs 函数是搜索的核心，x 表示小球在 x 轴的坐标，y 表示小球在 y 轴的坐标。

code

#include<bits/stdc++.h>
#define XD 114514
#define yee 1919810

using namespace std;
int n,m,k,a[1010][1010],ans;
void dfs(int x,int y){//搜索
    if(x>n or y>m){
        ans=y;
        return;
    }
    if(a[x][y]==1){//把小球向右移动
        a[x][y]=2;
        y++;
    }else if(a[x][y]==2){//把小球向下移动
        x++;
    }else if(a[x][y]==3){//把小球向左移动
        a[x][y]=2;
        y--;
    }
    dfs(x,y);
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=k;i++){
        int nem;
        scanf("%d",&nem);
        ans=0;//初始化，其实没有也可以
        dfs(1,nem);
        cout<<ans<<" ";
    }
    return 0;
}

AC记录