1 solutions
-
0
C++ :
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[100][100],ans,m,n; const int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; struct queh { int x,y; }que[100*100]; void init() { cin>>m>>n; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%1d",&a[i][j]); } } void bfs(int x,int y) { int head=0,tail=1; que[head].x=x,que[head].y=y; a[x][y]=0; while(head!=tail) { for(int i=0;i<4;i++) { int nx=que[head].x+dx[i],ny=que[head].y+dy[i]; if(a[nx][ny]&&nx>0&&ny>0&&nx<=m&&ny<=n) { //add(nx,ny); queh t; t.x=nx,t.y=ny; que[tail++]=t; a[nx][ny]=0; } } head++; } } void print() { printf("%d",ans); } int main() { init(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(a[i][j]!=0){ bfs(i,j); ans++; } print(); return 0; }
Pascal :
const dx:array[1..4]of longint=(1,-1,0,0); dy:array[1..4]of longint=(0,0,-1,1); var n,m,i,j,ans:longint; c:array[0..100,0..105]of char; b:array[0..100,0..105]of boolean; s:string; procedure dfs(x,y:longint); var i,h,t,x1,y1,tx,ty:longint; q:array[0..10000,1..2]of longint; begin h:=1;t:=1; q[t][1]:=x;q[t][2]:=y; b[x,y]:=true; while h<=t do begin x1:=q[h][1];y1:=q[h][2]; for i:=1 to 4 do begin tx:=x1+dx[i];ty:=y1+dy[i]; if (tx>0)and(tx<=n)and(ty>0)and(ty<=m)and(c[tx,ty]>'0') and(b[tx,ty]=false)then begin inc(t); q[t][1]:=tx;q[t][2]:=ty; b[tx,ty]:=true; end; end; inc(h); end; end; begin readln(n,m); for i:=1 to n do begin readln(s); for j:=1 to m do c[i,j]:=s[j]; end; fillchar(b,sizeof(b),false); for i:=1 to n do for j:=1 to m do if (c[i,j]>'0')and(b[i,j]=false)then begin dfs(i,j); inc(ans); end; writeln(ans); end.
Java :
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static char[][] map; static int[][] d; static int m,n; public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { m = in.nextInt(); n = in.nextInt(); map = new char[m][n]; d = new int[m][n]; for (int i = 0; i < m; i++) { String s = in.next(); for (int j = 0; j < n; j++) { map[i][j] = s.charAt(j); } } int cnt = 0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(map[i][j]!='0'&&d[i][j]==0) dfs(i,j,++cnt); } } System.out.println(cnt); } } public static void dfs(int r,int c,int id){ if(r<0||r>=m||c<0||c>=n) return; if(d[r][c]>0 || map[r][c]=='0') return; d[r][c] = id; dfs(r+1,c,id); dfs(r-1,c,id); dfs(r,c+1,id); dfs(r,c-1,id); } }
- 1
Information
- ID
- 665
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By