4 条题解
-
3
这题类似于鸣人与佐助
#include<bits/stdc++.h> using namespace std; int n,m,t,mx,my,zx,zy,dx[]{0,1,0,-1},dy[]{1,0,-1,0}; char g[205][205]; bool vis[205][205][15]; struct node{ int x,y,chake,step; }; bool check(int x,int y,int cha){ if(x<1||x>n||y<1||y>m)return 0; if(cha<0)return 0; if(vis[x][y][cha]==1)return 0; return 1; } void bfs(int x,int y,int cha){ queue<node> q; q.push(node{x,y,cha,0}); vis[x][y][cha]=1; while(!q.empty()){ node fr=q.front();q.pop(); if(fr.x==zx&&fr.y==zy){ cout<<fr.step; return; } for(int i=0;i<4;i++){ int nx=fr.x+dx[i]; int ny=fr.y+dy[i]; int cc=fr.chake; if(g[nx][ny]=='#'){ if(cc>=1)cc--; else continue; } if(check(nx,ny,cc)==1){ vis[nx][ny][cc]=1; q.push(node{nx,ny,cc,fr.step+1}); } } } cout<<-1; } int main(){ cin>>n>>m>>t; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>g[i][j]; if(g[i][j]=='@'){ mx=i; my=j; g[i][j]='*'; } if(g[i][j]=='o'){ zx=i; zy=j; g[i][j]='*'; } } } bfs(mx,my,t); return 0; } -
3
BFS:
#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MN=205; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct Node{int x,y,skill,time;}; char mp[MN][MN]; bool vis[MN][MN][10]; int M,N,S; int sx,sy; int BFS(){ queue<Node> q; q.push({sx,sy,S,0}); vis[sx][sy][S]=true; while(!q.empty()){ Node now=q.front(); q.pop(); if(mp[now.x][now.y]=='o'){ return now.time; } for(int i=0;i<4;i++){ int nx=now.x+dx[i]; int ny=now.y+dy[i]; int ns=now.skill; if(nx<0||nx>=M||ny<0||ny>=N) continue; char c=mp[nx][ny]; if(c=='#'){ if(ns<=0) continue; ns-=1; } if(!vis[nx][ny][ns]){ vis[nx][ny][ns]=true; q.push({nx,ny,ns,now.time+1}); } } } return -1; } int main(){ memset(vis,0,sizeof(vis)); cin>>M>>N>>S; for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ cin>>mp[i][j]; if(mp[i][j]=='@'){ sx=i; sy=j; } } } cout<<BFS()<<endl; return 0; }DFS(会超时):
#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MN=205; const int INF=0x3f3f3f3f; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; char mp[MN][MN]; //剩余s技能到(x,y)的最小时间 int dist[MN][MN][10]; int M,N,S; int sx,sy; //当前x,y，剩余技能k，当前已走时间t int dfs(int x,int y,int k,int t){ // 越界 if(x<0||x>=M||y<0||y>=N) return INF; // 该状态已有更短时间，直接剪枝 if(t>=dist[x][y][k]) return INF; // 更新当前状态最小时间 dist[x][y][k]=t; // 找到宝箱，返回当前步数 if(mp[x][y]=='o') return t; int res=INF; for(int i=0;i<4;i++){ int nx=x+dx[i]; int ny=y+dy[i]; int nk=k; char c=mp[nx][ny]; if(c=='#'){ if(nk<=0) continue; nk--; } res=min(res,dfs(nx,ny,nk,t+1)); } return res; } int main(){ memset(dist,0x3f,sizeof(dist)); cin>>M>>N>>S; for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ cin>>mp[i][j]; if(mp[i][j]=='@'){ sx=i;sy=j; } } } int ans=dfs(sx,sy,S,0); if(ans==INF) cout<<-1<<endl; else cout<<ans<<endl; return 0; } -
2
#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MAXM=205; const int MAXN=205; const int MAXSKILL=10; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct Node{int x,y,skill,time;}; char mp[MAXM][MAXN]; bool vis[MAXM][MAXN][MAXSKILL]; int M,N,S; int sx,sy; int BFS(){ queue<Node> q; q.push({sx,sy,S,0}); vis[sx][sy][S]=true; while(!q.empty()){ Node now=q.front(); q.pop(); if(mp[now.x][now.y]=='o'){ return now.time; } for(int i=0;i<4;i++){ int nx=now.x+dx[i]; int ny=now.y+dy[i]; int ns=now.skill; if(nx<0||nx>=M||ny<0||ny>=N) continue; char c=mp[nx][ny]; if(c=='#'){ if(ns<=0) continue; ns-=1; } if(!vis[nx][ny][ns]){ vis[nx][ny][ns]=true; q.push({nx,ny,ns,now.time+1}); } } } return -1; } int main(){ memset(vis,0,sizeof(vis)); cin>>M>>N>>S; for(int i=0;i<M;i++){ for(int j=0;j<N;j++){ cin>>mp[i][j]; if(mp[i][j]=='@'){ sx=i; sy=j; } } } cout<<BFS()<<endl; return 0; }
gf25030
GESP2&广附联赛3
LV 4
@ 2026-7-26 15:01:01
- 1
