滴滴笔试题

import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int [][]t=new int[n][m]; int [][]f=new int[n][m]; //ArrayList<Integer> [][] arrs=new ArrayList[n][m]; HashMap<Integer,HashSet<Integer>> hashMap=new HashMap(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { t[i][j]=sc.nextInt(); f[i][j]=i*m+j; if(t[i][j]==1) {HashSet<Integer> set=new HashSet(); set.add(i*m+j); hashMap.put(i*m+j, set); } } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(t[i][j]==1) { if(i-1>=0)//shang {if(t[i-1][j]==1) { if(f[i-1][j]<f[i][j]) { HashSet set=hashMap.get(f[i][j]); HashSet set2=hashMap.get(f[i-1][j]); set2.addAll(set); hashMap.put(f[i-1][j], set2); hashMap.remove(f[i][j]); f[i][j]=f[i-1][j]; } if(f[i-1][j]>f[i][j]) { HashSet set=hashMap.get(f[i][j]); HashSet set2=hashMap.get(f[i-1][j]); set.addAll(set2); hashMap.put(f[i][j], set); hashMap.remove(f[i-1][j]); f[i-1][j]=f[i][j]; } } } if(j-1>=0)//zuo {if(t[i][j-1]==1) { if(f[i][j-1]<f[i][j]) { HashSet set=hashMap.get(f[i][j]); HashSet set2=hashMap.get(f[i][j-1]); set2.addAll(set); hashMap.put(f[i][j-1], set2); hashMap.remove(f[i][j]); f[i][j]=f[i][j-1]; } if(f[i][j-1]>f[i][j]) { HashSet set=hashMap.get(f[i][j]); HashSet set2=hashMap.get(f[i][j-1]); set.addAll(set2); hashMap.put(f[i][j], set); hashMap.remove(f[i][j-1]); f[i][j-1]=f[i][j]; } } } } } } System.out.print(hashMap.size()); } }