1 条题解
-
0
这是一道按步走的bfs题目,对于每次询问,很容易知道,只要k与最短步数之差是偶数,就肯定满足k步到达目标点。
按步走有很多种方法实现,比如说
- 用结构体存储步数和x,y坐标
- 用一个新的二维数组存储每一个点的最小步数
- 在bfs的队列循环种添加步数变量(需要脑力足够,不然很容易出错)
每一种办法都可以用,能得到结果就好
#include<bits/stdc++.h> using namespace std; struct dian{ int x,y,bushu; }; int main() { int n,m;scanf("%d %d",&n,&m); int ydx[4]={0,0,1,-1}; int ydy[4]={1,-1,0,0}; vector<vector<char>> ditu(n,vector<char>(m)); vector<vector<bool>> vis(n,vector<bool>(m,false)); vector<vector<int>> shuzi(n,vector<int>(m,-1)); pair<int,int> qidian,zhongdian; for(int i=0;i<n;i++){ string s; cin>>s; for(int j=0;j<m;j++){ ditu[i][j]=s[j]; if(ditu[i][j]=='B'){ qidian={i,j}; } if(ditu[i][j]=='E'){ zhongdian={i,j}; } } } queue<dian> q; dian axx={qidian.first,qidian.second,0}; q.push(axx); vis[qidian.first][qidian.second]=true; shuzi[qidian.first][qidian.second]=0; while(!q.empty()){ auto acc=q.front(); q.pop(); for(int i=0;i<4;i++){ int nx=acc.x+ydx[i]; int ny=acc.y+ydy[i]; if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]&&ditu[nx][ny]!='#' &&shuzi[nx][ny]==-1){ shuzi[nx][ny]=acc.bushu+1; vis[nx][ny]=true; q.push({nx,ny,acc.bushu+1}); } } } int asdf; scanf("%d",&asdf); int bushushu=shuzi[zhongdian.first][zhongdian.second]; for(int i=0;i<asdf;i++){ long long k; cin>>k; if(bushushu==-1){ printf("NO\n"); } else if(k>=bushushu&&(k-bushushu)%2==0){ printf("YES\n"); } else{ printf("NO\n"); } } return 0; }
信息
- ID
- 626
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 478
- 已通过
- 51
- 上传者