1 solutions

  • 1
    @ 2021-11-29 19:03:36

    BFS流程步骤:

    1.首结点入队列并标记

    2.搜寻首结点的上,下,左,右结点,满足条件就入队列并标记

    3.首结点出队列,下一个结点成为首节点,计数器加一

    4.重复2,3步骤,直到队列中全部的结点出队列

    BFS

    #include <bits/stdc++.h>
    #include <queue>
    using  namespace std;
    int n, m, x, y, ans, cnt = 0;
    const int maxn = 1005;
    int area[maxn][maxn];
    int X[4] = {-1, 1, 0, 0}; //上下左右四个方向 
    int Y[4] = {0, 0, -1, 1};
    bool F[maxn][maxn] = {false};
    
    struct node {
    	int x;
    	int y;
    }Node, top;
    
    bool judge(int x, int y) {
    	if(x < 0 || y < 0 || x >= n || y >= m) //越界不入队列 
    	return false;
    	if(F[x][y] == true || area[x][y] == 0) //被选过了或者没有树不入队列 
    	return false; 
    	return true;
    }
    
    void BFS(int x, int y) {
    	queue<node> q;
    	Node.x = x;
    	Node.y = y;
    	q.push(Node);
    	while (!q.empty()) {
    		top = q.front();
    		int lx = top.x;
    		int ly = top.y;
    		for (int i = 0; i < 4; i++) {
    			if (judge(lx + X[i], ly + Y[i]))
    			{
    				Node.x = lx + X[i];
    				Node.y = ly + Y[i]; 
    				q.push(Node);
    				F[Node.x][Node.y] = true;
    			}
    		}
    		ans++;
    		F[lx][ly] = true;
    		q.pop();
    	}
    }
    
    int main() {
    	cin >> n >> m >> x >> y;
    	for (int i = 0; i < n; i ++) {
    		for (int j = 0; j < m; j++) {
    			cin >> area[i][j];
    			if (area[i][j] == 1) cnt++;
    		}
    	}
    	
    	if (area[x][y] == 1) {
    		BFS(x, y);
    	}
    	cout << ans << endl;
    	double rate = (double)ans / cnt;
    	if (rate >= 0.2)
    	cout << "获得成就:生 态 灭 绝 者";
    	else if (rate >= 0.1)
    	cout << "获得成就:伐伐伐伐伐木工";
    	else 
    	cout <<"获得成就:就这?"; 	
    		
    	
    	return 0;
    } 
    

    DFS

    #include<stdio.h>
    #include<iostream>
    using namespace std;
    const int N=1005;
    int n,m,k,fx,fy,ex,ey,sx,sy,ans,sum;
    double rate;
    int ma[N][N],mas[N][N];
    int opx[5]={1,-1,0,0};
    int opy[5]={0,0,-1,1};
    
    void dfs(int x,int y)
    {
    		int nx,ny;
    		for(int i=0;i<4;i++)
    		{
    			nx=x+opx[i];
    			ny=y+opy[i];
    			if(nx>=0&&nx<=n-1&&ny>=0&&ny<=m-1&&mas[nx][ny]==0&&ma[nx][ny]==1)
    			{
    				ans++;
    				mas[nx][ny]=1;
    				dfs(nx,ny);
    			}
    		}
    	
    }
    int main()
    {
    	scanf("%d %d",&n,&m);
    	scanf("%d %d",&sx,&sy);
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			scanf("%d",&ma[i][j]);
    			if(ma[i][j]==1) sum++;
    		}
    	}
    	if(ma[sx][sy]==1) 
    	{
            ans++;
    	    mas[sx][sy]=1;
    	    dfs(sx,sy);
    	}
    
    	rate=(double)ans/sum;
    	if(rate>=0.2)
    	{
    		printf("%d\n",ans);
    		printf("获得成就:生 态 灭 绝 者\n");
    	}
    	else if(rate<0.2&&rate>=0.1)
    	{
    		printf("%d\n",ans);
    		printf("获得成就:伐伐伐伐伐木工\n");
    	}
    	else
    	{
    		printf("%d\n",ans);
    		printf("获得成就:就这?\n");
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    184
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    154
    Accepted
    30
    Uploaded By