洛谷题单【算法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){//并不需要<=300return 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(){//更新陨石,所有不安全的点均有陨石,时间-1per(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;
}