@RiverHamster
2017-11-19T17:00:20.000000Z
字数 1778
阅读 10887
Luogu
DFS
连通块
楼下都说这题是什么并查集什么的,其实DFS联通块就可以了,没有那么复杂,速度也快。
时间:216ms
单个点时间:68ms
空间:36MB
时间复杂度O(n^2)+O(m)
很容易就可以发现,所有连接在一起的格子的答案是一样的。
所以,只需要用DFS找到所有的联通块,联通块内所有的格子的答案都是这个联通块的格子数目。
记录每个格子是否被搜过(在某个连通块中)。
两重循环,如果这格没搜过就从这个格子开始搜。
每搜到一个格子当前答案加1,数组记录当前格子位置,每次都向4个方向的满足条件的格子扩展。
搜完一块后把数组记录的格子的答案赋成连通块总的格子数。
读入时有个小技巧,对于二维字符数组a,scanf("%s",a[i]+1)
可以以1下标读入一行。
(gets,strlen等同理,如strlen(s+1)
1下标字符串长度)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(!v[i][j]){ //枚举格子,没有访问过就DFS
v[i][j]=true; //这格被访问
now=0; //总数记为0
dfs(i,j); //从这格开始搜索
for(int i=1;i<=now;i++) f[ans[i][0]][ans[i][1]]=now; //依次赋值,重复使用并没有问题
}
#define nx x+dx[i] //增量数组表示下一个的x
#define ny y+dy[i] //增量数组表示下一个的y
#define check(x,y) (x>0&&x<=n&&y>0&&y<=n) //越界检查
void dfs(int x,int y){
now++; //记录答案
ans[now][0]=x,ans[now][1]=y; //记录连通块的格子
for(int i=0;i<4;i++){ //搜索下一格
if(check(nx,ny)&&!v[nx][ny]&&a[x][y]!=a[nx][ny]){
//越界、访问、颜色判断
v[nx][ny]=true; //记录访问状态
dfs(nx,ny); //下一格
}
}
}
#include <stdio.h>
#include <ctype.h>
#define check(x,y) (x>0&&x<=n&&y>0&&y<=n)
#define nx (x+dx[i])
#define ny (y+dy[i])
char a[1005][1005]; int f[1005][1005]; bool v[1005][1005];
int n,m,dx[]={1,0,-1,0},dy[]={0,1,0,-1},now;
int ans[1000005][2],Count; //变量定义防止太长压了行
void dfs(int x,int y){
now++;
ans[now][0]=x,ans[now][1]=y;
for(int i=0;i<4;i++){
if(check(nx,ny)&&!v[nx][ny]&&a[x][y]!=a[nx][ny]){
v[nx][ny]=true;
dfs(nx,ny);
}
}
}
int res;
char ch;
inline int read(){
res=0;
while(isspace(ch=getchar()));
do res=res*10+ch-'0'; while(isdigit(ch=getchar()));
return res;
}
inline void write(int n){
if(n==0) return;
write(n/10);
putchar(n%10+'0');
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(!v[i][j]){
v[i][j]=true;now=0;
dfs(i,j);
for(int i=1;i<=now;i++) f[ans[i][0]][ans[i][1]]=now;
}
register int x,y;
for(int i=1;i<=m;i++){
x=read();y=read();
write(f[x][y]);
putchar('\n');
}
return 0;
}