首页 > 拼多多9.1客户端笔试第二道编程题java版题解
头像
Sirius865
编辑于 2020-09-03 22:05
+ 关注

拼多多9.1客户端笔试第二道编程题java版题解

  1. 第二题,棋盘中移动一个点,使得连通块最大
  2. import java.util.*;
  3. public class maxCounting {
  4. static int n,m,N=410,idx=0;
  5. static int[][] g=new int[N][N];
  6. static int[][] w=new int[N][N];
  7. static boolean[][] st=new boolean[N][N];
  8. static Queue<Integer> queue=new LinkedList<>();
  9. static int[] cnt=new int[N*N];
  10. static int[][] directions={{1,0},{-1,0},{0,1},{0,-1}};
  11. public static void bfs(int sx,int sy){
  12. int ele=sx*N+sy;
  13. queue.offer(ele);
  14. w[sx][sy]=idx;
  15. st[sx][sy]=true;
  16. while(!queue.isEmpty()){
  17. int temp=queue.poll();
  18. int x=temp/N,y=temp%N;
  19. cnt[idx]++;
  20. for(int i=0;i<4;i++){
  21. int newX=x+directions[i][0],newY=y+directions[i][1];
  22. if(newX<0||newX>=n||newY<0||newY>=m) continue;
  23. if(g[newX][newY]==0||st[newX][newY]) continue;
  24. w[newX][newY]=idx;
  25. queue.offer(newX*N+newY);
  26. st[newX][newY]=true;
  27. }
  28. }
  29. }
  30. public static void main(String[] args) {
  31. Scanner scanner=new Scanner(System.in);
  32. n=scanner.nextInt();
  33. m=scanner.nextInt();
  34. for(int i=0;i<n;i++)
  35. for(int j=0;j<m;j++){
  36. g[i][j]=scanner.nextInt();
  37. }
  38. for(int i=0;i<n;i++)
  39. for(int j=0;j<m;j++){
  40. if(g[i][j]==0)continue;
  41. if(st[i][j]) continue;
  42. idx++;
  43. bfs(i,j);
  44. }
  45. int res=0;
  46. for(int i=0;i<n;i++)
  47. for(int j=0;j<m;j++){
  48. if(g[i][j]==1) continue;
  49. int ans=0;
  50. HashSet<Integer> set=new HashSet<>();
  51. for(int k=0;k<4;k++){
  52. int xx=i+directions[k][0],yy=j+directions[k][1];
  53. if(xx<0||xx>=n||yy<0||yy>=m) continue;
  54. if(w[xx][yy]==0) continue;
  55. if(set.contains(w[xx][yy])) continue;
  56. ans+=cnt[w[xx][yy]];
  57. set.add(w[xx][yy]);
  58. }
  59. if(set.size()<idx) ++ans;
  60. res=Math.max(res,ans);
  61. }
  62. System.out.println(res);
  63. }
  64. https://www.nowcoder.com/discuss/495707把这位老哥的C++题解翻译成了java版本

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐