- 第二题，棋盘中移动一个点，使得连通块最大
- import java.util.*;
- public class maxCounting {
- static int n,m,N=410,idx=0;
- static int[][] g=new int[N][N];
- static int[][] w=new int[N][N];
- static boolean[][] st=new boolean[N][N];
- static Queue<Integer> queue=new LinkedList<>();
- static int[] cnt=new int[N*N];
- static int[][] directions={{1,0},{-1,0},{0,1},{0,-1}};
- public static void bfs(int sx,int sy){
- int ele=sx*N+sy;
- queue.offer(ele);
- w[sx][sy]=idx;
- st[sx][sy]=true;
- while(!queue.isEmpty()){
- int temp=queue.poll();
- int x=temp/N,y=temp%N;
- cnt[idx]++;
- for(int i=0;i<4;i++){
- int newX=x+directions[i][0],newY=y+directions[i][1];
- if(newX<0||newX>=n||newY<0||newY>=m) continue;
- if(g[newX][newY]==0||st[newX][newY]) continue;
- w[newX][newY]=idx;
- queue.offer(newX*N+newY);
- st[newX][newY]=true;
- }
- }
- }
- public static void main(String[] args) {
- Scanner scanner=new Scanner(System.in);
- n=scanner.nextInt();
- m=scanner.nextInt();
- for(int i=0;i<n;i++)
- for(int j=0;j<m;j++){
- g[i][j]=scanner.nextInt();
- }
- for(int i=0;i<n;i++)
- for(int j=0;j<m;j++){
- if(g[i][j]==0)continue;
- if(st[i][j]) continue;
- idx++;
- bfs(i,j);
- }
- int res=0;
- for(int i=0;i<n;i++)
- for(int j=0;j<m;j++){
- if(g[i][j]==1) continue;
- int ans=0;
- HashSet<Integer> set=new HashSet<>();
- for(int k=0;k<4;k++){
- int xx=i+directions[k][0],yy=j+directions[k][1];
- if(xx<0||xx>=n||yy<0||yy>=m) continue;
- if(w[xx][yy]==0) continue;
- if(set.contains(w[xx][yy])) continue;
- ans+=cnt[w[xx][yy]];
- set.add(w[xx][yy]);
- }
- if(set.size()<idx) ++ans;
- res=Math.max(res,ans);
- }
- System.out.println(res);
- }
- https://www.nowcoder.com/discuss/495707把这位老哥的C++题解翻译成了java版本
近期热帖
近期精华帖
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
全部评论
(1) 回帖