2 条题解
-
1
深搜法
#include <bits/stdc++.h> using namespace std; int a[1010][1010],p1,p2,n,m,c=1; int fx[5]={0,0,0,-1,1}; int fy[5]={0,1,-1,0,0}; void dfs(int x,int y,int s){ a[x][y]=INT_MAX; int tx,ty; for(int i=1;i<=4;i++){ tx=x+fx[i]; ty=y+fy[i]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]<=s){ c++; dfs(tx,ty,s); } } } int main() { cin>>n>>m>>p1>>p2; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } dfs(p1,p2,a[p1][p2]); cout<<c; return 0; }
广搜法
#include <bits/stdc++.h> using namespace std; int a[1010][1010],p1,p2,n,m,c=1,t,h; int q[1000010][3]; int fx[5]={0,0,0,-1,1}; int fy[5]={0,1,-1,0,0}; bool f[1010][1010]; int main() { cin>>n>>m>>p1>>p2; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } h=t=1; q[h][1]=p1; q[h][2]=p2; f[p1][p2]=true; int tx,ty; while(h<=t){ for(int i=1;i<=4;i++){ tx=fx[i]+q[h][1]; ty=fy[i]+q[h][2]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]<=a[p1][p2]&&!f[tx][ty]){ t++; q[t][1]=tx; q[t][2]=ty; f[tx][ty]=true; } } h++; } cout<<t; return 0; }
已经AC,放心使用你的应急食品
-
0
#include <bits/stdc++.h> using namespace std; int n,m,p1,p2,tx,ty,a[110][110],ans=1; int fx[5]={0,0,1,0,-1}; int fy[5]={0,1,0,-1,0}; bool f[110][110]; struct bfs{ int x,y; }r; queue<bfs>q; int main(){ cin>>n>>m>>p1>>p2; for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++)cin>>a[i][j]; } r.x=p1; r.y=p2; q.push(r); f[1][1]=true; while(!q.empty()){ for (int i=1;i<=4;i++){ tx=q.front().x+fx[i]; ty=q.front().y+fy[i]; if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&!f[tx][ty]&&a[tx][ty]<=a[p1][p2]){ r.x=tx; r.y=ty; q.push(r); f[tx][ty]=true; ans++; } } q.pop(); } cout<<ans; return 0; }
- 1
信息
- ID
- 440
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 30
- 已通过
- 21
- 上传者