首页 > 其他分享 >Living-Dream 系列笔记 第11期

Living-Dream 系列笔记 第11期

时间:2024-03-09 12:36:22浏览次数:26  
标签:11 Living 连通 int yy vis && 1031 Dream

本期主要讲解与上期相同内容(雾。

例题

T1

在整个矩阵外加一圈 \(0\),使得包围圈外的 \(0\) 形成一整个连通块。求出这个连通块并标记为 \(1\),然后输出即可。

#include<bits/stdc++.h>
using namespace std;

int n;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int a[31][31],g[31][31];

void dfs(int x,int y){
    if(x<0||x>n+1||y<0||y>n+1||g[x][y]!=0) return;
    g[x][y]=1;
    for(int i=0;i<4;i++) dfs(x+dx[i],y+dy[i]);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(!a[i][j]) g[i][j]=0;
            else g[i][j]=1;
        }
    }
    dfs(0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!g[i][j]) cout<<"2 ";
            else cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

T2

求连通块很简单,本题的难点在于所有连通块必须为矩形。

如图,一个不是矩形的连通块可以看作是几个相邻的矩形拼凑在一起组成的。

而两个相邻矩形之间会形成一些的“拐角”,即在一个 \(2 \times 2\) 的正方形中的三个角是 #,而一个角是 .

由此,我们便可枚举整个矩阵中所有 \(2 \times 2\) 的矩形,若产生了“拐角”,则直接输出 Bad placement. 即可。

我的代码并未全面判断,但是却过了 \(qwq\),说明数据太水了

#include<bits/stdc++.h>
using namespace std;

int r,c,ans;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool vis[1031][1031];
char a[1031][1031];

void dfs(int x,int y){
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=1&&xx<=r&&yy>=1&&yy<=c&&a[xx][yy]=='#'&&!vis[xx][yy])
            dfs(xx,yy);
    }
}

int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>a[i][j];
            
    bool f=1;
    for(int i=1;i+1<=r;i++)
        for(int j=1;j+1<=c;j++){
            if(a[i][j]=='#'&&a[i+1][j]=='#'&&a[i][j+1]=='#'&&a[i+1][j+1]!='#'){
                f=0; break;
            }
            if(a[i][j]!='#'&&a[i+1][j]=='#'&&a[i][j+1]=='#'&&a[i+1][j+1]=='#'){
                f=0; break;
            }
        }
    if(!f){ cout<<"Bad placement."; return 0; }
    
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            if(a[i][j]=='#'&&!vis[i][j])
                ans++,dfs(i,j);
    cout<<"There are "<<ans<<" ships.";
    return 0;
}

T3

只有 shaber 才会去想到对于每次询问进行 \(\text{DFS}\) 求出连通块大小(没错说的就是我)。

考虑优化搜索。我们想到,因为连通块始终是不变的,所以我们可以进行预处理。

具体的,我们对每个连通块存入 \(ans\) 数组并依次对其编号,并在搜索连通块的过程中顺便对于每个点 \((x,y)\) 求出包含它的连通块编号 \(id\),存入 \(pos_{x,y}\) 中。

这样,我们便实现了 \(O(1)\) 回答每次询问,总的时间复杂度为 \(O(n^2+m)\)。

最后,需要注意的是:

  • 连通块个数 \(num\) 每次预处理前必须初始化为 \(1\);

  • 因为读入的矩阵无空格,所以需要使用 \(char\) 类型保存矩阵。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,id,num;
int ans[1000031],pos[1031][1031];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool vis[1031][1031];
char a[1031][1031];

void dfs(int x,int y){
    vis[x][y]=1,pos[x][y]=id;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]&&a[xx][yy]!=a[x][y])
            num++,dfs(xx,yy);
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
        	if(!vis[i][j]){
        		id++,num=1;
        		dfs(i,j);
        		ans[id]=num;
        	}
		}
    while(m--){
        int x,y; cin>>x>>y; cout<<ans[pos[x][y]]<<'\n';
    }
    return 0;
}

习题

T4

求周长参考上期 T5。

注意点就是需要向八方向搜索,并且只有当扩展方向为上 / 下 / 左 / 右且即将扩展的点为 . 或越界了,才能将周长累加。

#include<bits/stdc++.h>
using namespace std;

int n;
char ice[1031][1031];
int S,C,s,c;
bool vis[1031][1031];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

void update(){
    if(s>S) S=s,C=c;
    if(s==S&&c<C) C=c;
}
void dfs(int x,int y){
    if(vis[x][y]) return;
    vis[x][y]=1,s++;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>n||ice[xx][yy]=='.') c++;
        if(ice[xx][yy]=='#') dfs(xx,yy);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>ice[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ice[i][j]=='#'&&!vis[i][j]){
            	s=c=0;
                dfs(i,j);
                update();
            }
        }
    }
    cout<<S<<' '<<C;
    return 0;
}

标签:11,Living,连通,int,yy,vis,&&,1031,Dream
From: https://www.cnblogs.com/XOF-0-0/p/18062515

相关文章

  • Living-Dream 系列笔记 第12期
    本期主要讲解一维前缀和技巧。知识点我们令\(a_i\)表示原数组的第\(i\)个元素,则\(sum_i\)表示\(a_i\)前\(i\)个元素之和,即:\[sum_i=\sum^{i}_{j=1}a_j\]我们知道,\(a\)数组前\(i\)个元素的和\(=\)前\(i-1\)个元素的和\(+a_i\)。于是便可得到\(sum\)数组的......
  • Living-Dream 系列笔记 第13期
    本期主要讲解二维前缀和。知识点我们令\(a_{i,j}\)表示原数组,则\(sum_{i,j}\)为\(a\)的二维前缀和数组。根据容斥原理,得到递推式:\[sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j}\]二维前缀和适用于求静态矩阵的子矩阵元素和。若我需要求一个左上角坐标为......
  • Living-Dream 系列笔记 第10期
    本期主要讲解进阶\(\text{DFS}\)。知识点\(\text{DFS}\)求解连通块问题:定义:若一个点集中的所有点都能互达,且与集合外的点无法互达,则称此点集为一个连通块。考查方式:求连通块数量/大小/周长。例题T1在\(\text{DFS}\)函数中传入参数\(x\)和\(str\),分别表示......
  • Living-Dream 系列笔记 第8期
    本期主要讲解的与上期相同。例题T1上课的时候调这个题感觉要吐了\(qwq\)。。。首先读入\(n\)行字符串,可以采取忽略中间无关单词的方式来直接读取\(X\)和\(Y\)。将所有名字存入\(a\)数组,对\(a\)数组按字典序排序后就可以开始\(\text{DFS}\)了,这里建议使用next_pr......
  • Living-Dream 系列笔记 第9期
    模拟赛掉大分(悲T1板子,不讲。T2首先很明显这题是个去重全排列。和模板的区别就是加了一个\(sum\)参数记录目前已经放了几个苹果。当\(x=n+1\)时若\(sum=m\),则更新答案。同时加入一个剪枝:若在搜索过程中\(sum>m\),则直接return结束搜索。#include<bits/stdc++.h>usi......
  • Living-Dream 系列笔记 第6期
    模拟赛。寄。T1对于每次询问,二分查找数组中对应值的原下标即可,因此需要用结构体存储原始数据和原始下标。这当然是比较麻烦的做法。另一种做法则是开一个map替代桶来存储数组中每个元素的下标,对于每个询问输出即可。另外值得注意的是,本题默认询问之间相互独立。时间复杂度......
  • Living-Dream 系列笔记 第7期
    本期主要讲解深度优先搜索\(\text{DFS}\)。知识点种类:全排列。可以想象为填格子。去重全排列,即组合。时间复杂度均为\(O(n!)\)。\(\text{DFS}\)题的特征:求方案总数/最值。数据范围极小(一般\(n\le20\))。无法直接暴力枚举(因为循环嵌套层数不确定)。......
  • Living-Dream 系列笔记 第4期
    本期主要讲解二分答案。知识点使用场景:最小值最大化,或最大值最小化。在限制条件下找最值。与二分查找的区别:L、R均为答案,而非下标。输出:最大化输出L,反之输出R。例题T1二分\(M\)的值,边界为\(L=-1,R=\max{\{a_i\}}\)。每次枚举到一个\(mid\)就对于每个......
  • Living-Dream 系列笔记 第5期
    本期主要讲解二分答案的进阶。例题T1二分需要的秒数,在check函数中对于每件衣服,若其在\(x\)秒内无法自然晒干,则使用烘干机,并令\(sum\)加上使用烘干机的秒数,最后判断\(sum\)是否\(\lex\)即可。\(Trick\):二分边界需要按数据范围尽可能开大,不能开小了。#include<bits/......
  • docekr-debian 11(bullseye)
    cat>/etc/apt/sources.list<<EOF#默认注释了源码镜像以提高aptupdate速度,如有需要可自行取消注释debhttps://mirrors.tuna.tsinghua.edu.cn/debian/bullseyemaincontribnon-free#deb-srchttps://mirrors.tuna.tsinghua.edu.cn/debian/bullseyemaincontribnon-......