网站建设与管理 自考,厦门公司网站建设,十堰的网络优化公司,周浦做网站公司P1135 奇怪的电梯
一开始以为深搜肯定没问题#xff0c;从a点出发#xff0c;衍生出一个二叉树#xff0c;遍历所有情况就好了#xff0c;但是会重复#xff0c;所以加了一个vis防止重复#xff0c;但是只拿了64pts#xff0c;因为有可能某个点并不是最短被到达的…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 N2005;
int n,k[N],a,b,ansINT_MAX,dis[N];void dfs(int x,int step){if(x1 or xn or stepdis[x] or stepans)return;if(xb)return ansstep,void();dis[x]step;dfs(xk[x],step1);dfs(x-k[x],step1);
}void solve(){cinnab;per(i,1,n)cink[i],dis[i]INT_MAX;dfs(a,0);ansansINT_MAX?-1:ans;coutansendl;
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t1;while(t--)solve();return 0;
} P2895 [USACO08FEB] Meteor Shower S
坑也太多了下面列举一下坑题不是很难就模拟BFS。
1. 流星只会在0x3000y300出现但是没说人不能走出这个范围人在第一象限移动
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 piipairint,int;const int N3005;
int m,x,y,t,a[N][N],step[N][N],dx[4]{0,0,1,-1},dy[4]{1,-1,0,0},cnt1,precnt;
bool vis[N][N];bool isingrid(pii x){//并不需要300return x.fr0 and x.se0 ;
}bool safe(pii x){//输入的时候已经延伸陨石了,所以判断的时候不需要延伸if(a[x.fr][x.se]!SAFE)return false;else return true;
}void ans(pii x){coutstep[x.fr][x.se]endl;
}void noans(){cout-1endl;
}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;//标记为安全cinm;per(i,1,m){cinxyt;a[x][y]min(a[x][y],t);//有陨石就不安全,标记一下降落时间取最早时间per(j,0,3){//四个方向都标记pii nxt{xdx[j],ydy[j]};if(isingrid(nxt)){//范围是否合法a[nxt.fr][nxt.se]min(a[nxt.fr][nxt.se],t);}}}queuepiiq;q.push({0,0});while(!q.empty()){pii nowq.front();q.pop();cnt--;vis[now.fr][now.se]true;if(safe(now))return ans(now);//当前点安全输出答案per(i,0,3){pii nxt{now.frdx[i],now.sedy[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(cnt0){//若每一层遍历cnt都用完了,则说明要更新陨石降落时间cntprecnt;precnt0;updateMeteor();}}return noans();//无路可走,没有答案
}signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);int t1;while(t--)solve();return 0;
}
