题目请点这里 https://ac.nowcoder.com/acm/contest/332/J
分析: 这是一道 BFS 的模板题, 构造一个队列, 将每个满足条件的 (不超过边界, 不超过左右移动次数的限制) 位置推入队列, 如果不是障碍物且没到达过, 就将可到达位置的个数加 1
此外, 注意这里的输入, 输入迷宫的时候是直接输字符串, 可以用 cin, 也可以用 getchar()函数
getchar()函数是遇到回车符才会停止, 但是它的返回值只有首字符, 其他字符都存在缓存区, 我们便可以在第一个循环里放一个 getchar()来处理回车符, 在第二层循环里, 实际上只在 j=1 的时候有输入,
其他时候只不过是读入 j=1 时存在缓存区里的字符
上代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int inf=1<<30;
- typedef long long ll;
- const double pi=acos(-1);
- const int mod=1e9+7;
- const int maxn=1010;
- char a[maxn][maxn];
- int vis[maxn][maxn];
- struct node{
- int x,y,lx,ly;
- node(int x,int y,int lx,int ly): x(x),y(y),lx(lx),ly(ly){}
- };
- queue<node> q;
- int main(){
- int n,m,r,c,x,y;scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
- for(int i = 1; i <= n; i++) {
- getchar();
- for(int j = 1; j <= m; j++)
- a[i][j] = getchar();
- }
- int ans=0;
- q.push(node(r,c,x,y));
- while(!q.empty()){
- node u=q.front();q.pop();
- if(vis[u.x][u.y]||a[u.x][u.y]=='*'){
- continue;
- }
- vis[u.x][u.y]=1;ans++;
- if(u.x>1) q.push(node(u.x-1,u.y,u.lx,u.ly));
- if(u.x<n) q.push(node(u.x+1,u.y,u.lx,u.ly));
- if(u.y>1&&u.lx>0) q.push(node(u.x,u.y-1,u.lx-1,u.ly));
- if(u.y<m&&u.ly>0) q.push(node(u.x,u.y+1,u.lx,u.ly-1));
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2944213.html