首页 > 代码库 > NYOJ题目27水池数目
NYOJ题目27水池数目
---------------------------------------------
这道题有点坑,也怪我总是有点马虎,按照正常人的思维0是表示有水池啊竟然是1表示有水池,最坑的是写反了竟然还能过样例一直以为是自己程序问题review了好多遍....
图论基础题,染色法即可。
AC代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int times=sc.nextInt(); while(times-->0){ int n=sc.nextInt(); int m=sc.nextInt(); map=new int[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ map[i][j]=sc.nextInt(); } } int color=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(map[i][j]==1) dfs(i,j,--color); } } System.out.println(-color); } } public static int map[][]; public static int next[][]={{-1,0},{0,1},{1,0},{0,-1}}; public static void dfs(int x,int y,int color){ if(x<0 || x>=map.length || y<0 || y>=map[x].length) return ; if(map[x][y]==1){ map[x][y]=color; for(int i=0;i<next.length;i++){ int nx=x+next[i][0]; int ny=y+next[i][1]; dfs(nx,ny,color); } } } }
题目来源: http://acm.nyist.net/JudgeOnline/problem.php?pid=27
NYOJ题目27水池数目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。