2 条题解

  • 0
    @ 2024-3-16 18:09:56

    深搜法

    #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
      @ 2024-2-15 13:14:57
      #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
      标签
      递交数
      26
      已通过
      18
      上传者