题解 UVA11244()

题解UVA11244

题目大意：判断大小为 连通块有几个

1

这个题说实话真的挺水的，你可以考虑用 来判断联通块然后记录大小

dfs

这只是其中一个思路，另一个思路是，直接判断 的 连通里有没有其他的 

*
8
*

这个的复杂度明显是 \(O(8NM)\),按理说应该比 要快很多

dfs

但是不知道是因为 的评测机跑得太快还是其他原因， 直接跑进 

UVA
dfs
10ms

这是 评测记录

dfs

以下是 代码

dfs
#include<cstdio>
#include<string.h>
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m,cnt,ans;
int a[N][N],vis[N][N];
int dx[9]{0,0,0,1,-1,1,1,-1,-1};
int dy[9]{0,1,-1,0,0,1,-1,-1,1};
void dfs(int x,int y){
	for(int i=1;i<=8;i++){
		int fx=dx[i]+x,fy=dy[i]+y;
		if(!vis[fx][fy] && a[fx][fy] && fx>0 && fy>0 && fx<=n && fy<=m){
			cnt++;
			vis[fx][fy]=1;
			dfs(fx,fy);
		}
	}
}
int main(){
	while(scanf("%d%d",&n,&m)){
		ans=0;
		memset(a,0,sizeof a);
		memset(vis,0,sizeof vis);
		if(n==0 || m==0){
			return 0;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char c;
				cin>>c;
				if(c=='*'){
					a[i][j]=1;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cnt=1;
				if(!vis[i][j] && a[i][j]){
					vis[i][j]=1;
					dfs(i,j);
					if(cnt==1){
						ans++;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

这是 另一种做法的评测记录

以下是其代码

#include<cstdio>
#include<string.h>
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m,cnt,ans;
int a[N][N],vis[N][N];
int dx[9]{0,0,0,1,-1,1,1,-1,-1};
int dy[9]{0,1,-1,0,0,1,-1,-1,1};
int main(){
	while(scanf("%d%d",&n,&m)){
		ans=0;
		memset(a,0,sizeof a);
		if(n==0 || m==0){
			return 0;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char c;
				cin>>c;
				if(c=='*'){
					a[i][j]=1;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				bool f=1;
				if(a[i][j]){
					for(int k=1;k<=8;k++){
						int fx=dx[k]+i,fy=dy[k]+j;
						if(a[fx][fy]==1 && fx<=n && fy<=m && fx>0 && fy>0){
							f=0;
							break ; 
						}
					}
					if(f==1){
						ans++;
					}
				}				
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
————————

题解UVA11244

题目大意：判断大小为 连通块有几个

1

这个题说实话真的挺水的，你可以考虑用 来判断联通块然后记录大小

dfs

这只是其中一个思路，另一个思路是，直接判断 的 连通里有没有其他的 

*
8
*

这个的复杂度明显是 \(O(8NM)\),按理说应该比 要快很多

dfs

但是不知道是因为 的评测机跑得太快还是其他原因， 直接跑进 

UVA
dfs
10ms

这是 评测记录

dfs

以下是 代码

dfs
#include<cstdio>
#include<string.h>
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m,cnt,ans;
int a[N][N],vis[N][N];
int dx[9]{0,0,0,1,-1,1,1,-1,-1};
int dy[9]{0,1,-1,0,0,1,-1,-1,1};
void dfs(int x,int y){
	for(int i=1;i<=8;i++){
		int fx=dx[i]+x,fy=dy[i]+y;
		if(!vis[fx][fy] && a[fx][fy] && fx>0 && fy>0 && fx<=n && fy<=m){
			cnt++;
			vis[fx][fy]=1;
			dfs(fx,fy);
		}
	}
}
int main(){
	while(scanf("%d%d",&n,&m)){
		ans=0;
		memset(a,0,sizeof a);
		memset(vis,0,sizeof vis);
		if(n==0 || m==0){
			return 0;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char c;
				cin>>c;
				if(c=='*'){
					a[i][j]=1;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cnt=1;
				if(!vis[i][j] && a[i][j]){
					vis[i][j]=1;
					dfs(i,j);
					if(cnt==1){
						ans++;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

这是 另一种做法的评测记录

以下是其代码

#include<cstdio>
#include<string.h>
#include<cstring>
#include<iostream>
using namespace std;
const int N=110;
int n,m,cnt,ans;
int a[N][N],vis[N][N];
int dx[9]{0,0,0,1,-1,1,1,-1,-1};
int dy[9]{0,1,-1,0,0,1,-1,-1,1};
int main(){
	while(scanf("%d%d",&n,&m)){
		ans=0;
		memset(a,0,sizeof a);
		if(n==0 || m==0){
			return 0;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char c;
				cin>>c;
				if(c=='*'){
					a[i][j]=1;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				bool f=1;
				if(a[i][j]){
					for(int k=1;k<=8;k++){
						int fx=dx[k]+i,fy=dy[k]+j;
						if(a[fx][fy]==1 && fx<=n && fy<=m && fx>0 && fy>0){
							f=0;
							break ; 
						}
					}
					if(f==1){
						ans++;
					}
				}				
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}