洛谷题单【算法1-7】搜索

P1135 奇怪的电梯

一开始以为深搜肯定没问题，从a点出发，衍生出一个二叉树，遍历所有情况就好了，但是会重复，所以加了一个vis防止重复，但是只拿了64pts，因为有可能某个点并不是最短被到达的，但是已经被标记上了vis，所以如果要遍历这一个整个合法的最短二叉树，应该要用BFS。

DFS的话因为是一直在搜，所以加一个dis数组，更新每个点的最短次数。

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define se second
#define endl '\n'
using namespace std;

const int N=200+5;
int n,k[N],a,b,ans=INT_MAX,dis[N];

void dfs(int x,int step){
	if(x<1 or x>n or step>=dis[x] or step>=ans)return;
	if(x==b)return ans=step,void();
	dis[x]=step;
    dfs(x+k[x],step+1);
    dfs(x-k[x],step+1);
}

void solve(){
    cin>>n>>a>>b;
    per(i,1,n)cin>>k[i],dis[i]=INT_MAX;
    dfs(a,0);
    ans=ans==INT_MAX?-1:ans;
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}

P2895 [USACO08FEB] Meteor Shower S

坑也太多了，下面列举一下坑，题不是很难，就模拟+BFS。

1. 流星只会在0<=x<=300，0<=y<=300出现，但是没说人不能走出这个范围，人在第一象限移动

2. 多个流星降落的点，要取最早的那一个

3. 每个点最多被走一次，如果返回来走第二次，肯定不会更优，重复走还会MLE

4. 陨石还有2降落的时候才能走那个点，走上去1，走出去0，如果是1走进去就被砸了

#include <bits/stdc++.h>
//#define int long long
#define per(i,j,k) for(int (i)=(j);(i)<=(k);++(i))
#define rep(i,j,k) for(int (i)=(j);(i)>=(k);--(i))
#define fr first
#define SAFE INT_MAX
#define se second
#define endl '\n'
using namespace std;
using pii=pair<int,int>;

const int N=300+5;
int m,x,y,t,a[N][N],step[N][N],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},cnt=1,precnt;
bool vis[N][N];

bool isingrid(pii x){//并不需要<=300
    return x.fr>=0 and x.se>=0 ;
}

bool safe(pii x){//输入的时候已经延伸陨石了,所以判断的时候不需要延伸
    if(a[x.fr][x.se]!=SAFE)return false;
    else return true;
}

void ans(pii x){
    cout<<step[x.fr][x.se]<<endl;
}

void noans(){
    cout<<-1<<endl;
}

void updateMeteor(){//更新陨石,所有不安全的点均有陨石,时间-1
    per(i,0,304)per(j,0,304)if(a[i][j]!=SAFE)a[i][j]--;
}

void solve(){
    per(i,0,304)per(j,0,304)a[i][j]=SAFE;//标记为安全

    cin>>m;
    per(i,1,m){
        cin>>x>>y>>t;
        a[x][y]=min(a[x][y],t);//有陨石就不安全,标记一下降落时间，取最早时间
        per(j,0,3){//四个方向都标记
            pii nxt={x+dx[j],y+dy[j]};
            if(isingrid(nxt)){//范围是否合法
                a[nxt.fr][nxt.se]=min(a[nxt.fr][nxt.se],t);
            }
        }
    }

    queue<pii>q;
    q.push({0,0});
    while(!q.empty()){
        pii now=q.front();q.pop();cnt--;
        vis[now.fr][now.se]=true;

        if(safe(now))return ans(now);//当前点安全，输出答案
        per(i,0,3){
            pii nxt={now.fr+dx[i],now.se+dy[i]};
            if(isingrid(nxt) and a[nxt.fr][nxt.se]>=2 and !vis[nxt.fr][nxt.se]){
                q.push(nxt),precnt++;//记录一下进队的数量
                step[nxt.fr][nxt.se]=step[now.fr][now.se]+1;
                vis[nxt.fr][nxt.se]=true;//标记一下被使用过了,不要重复走,不然会MLE
            }
        }

        if(cnt==0){//若每一层遍历cnt都用完了,则说明要更新陨石降落时间
            cnt=precnt;
            precnt=0;
            updateMeteor();
        }
    }

    return noans();//无路可走,没有答案
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t=1;
    while(t--)solve();
    return 0;
}