2 条题解

  • 0
    @ 2022-12-10 8:55:10

    难度不大啊,主要是读题困难(反正我觉得是) 这道题不能深搜哦,只能用广搜做,因为广搜是广度遍历。

    加100是怕坐标为负数

    #include<iostream>
    #include<cstring>
    #include<queue>
    using namespace std;
    int n,m,t;
    struct node{
        int x,y;
    };
    /*
    9 9
    1
    5 5
    */
    int step=0;
    
    bool ans1[1309][1309];
    bool vis[1309][1309];
    int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
    void bfs(int x,int y){
    	memset(vis,0,sizeof vis);
    	step=1;
        queue<node>q;
        q.push((node){x+100,y+100});
        vis[x+100][y+100]=1;
        ans1[x+100][y+100]=1;
        while(!q.empty()){
        	if(step>=41){
                return ;
            }
            node p=q.front();
            q.pop();
            if(step>=41){
                return ;
            }
            for(int i=0;i<4;i++){
                int xx=dx[i]+p.x;
                int yy=dy[i]+p.y;
                //cout<<xx<<" "<<yy<<endl;;
                if(xx<0||yy<0||xx>n+200||yy>m+200||vis[xx][yy]==1){
                	continue;
    			}
    		//	cout<<"IAK";
    			vis[xx][yy]=1;//
    			ans1[xx][yy]=1;
                step++;
                if(step>=41){
               		return ;
            	}
                //cout<<step<<" ";
    			q.push((node){xx,yy});
            }
        }
    }
    int main(){
        cin>>n>>m>>t;
        for(int i=1;i<=t;i++){
        	int x,y;
            cin>>x>>y;
            vis[x+100][y+100]=1;
            ans1[x+100][y+100]=1;
            bfs(x,y);
        }
        int ans=0;
        for(int i=101;i<=n+100;i++){
        	for(int j=101;j<=m+100;j++){
       		if(ans1[i][j]==0){
        		//	cout<<".";
    			}
    			else {
    			//	cout<<ans1[i][j];
    			//	continue;
    //				if(vis[i][j]==2){
    //					continue;
    //				}
    				ans++;
    			}
    		}
    	//	cout<<endl;
    	}
    	cout<<ans;
    }
    

    信息

    ID
    16
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    40
    已通过
    10
    上传者