一道面试题，求解
连通判定，图1为连通（从一个[1]可以到达任何一个[1]）
图2为不连通（至少存在2个[1],他们之间无法到达）
图1：
1 1 1 1 1 1 1
1 1 1 1 0 0 1
1 1 1 1 0 0 1
1 1 0 0 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
图2:
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
1 0 1 1 1 0 1
1 0 1 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
Class Con
{
int array[m][n];
Public bool check()
{
//连通判定逻辑
}
}
--------------------编程问答--------------------
开眼了。。。帮顶
--------------------编程问答--------------------
求解啊 怎么没人呢
--------------------编程问答--------------------
代码很恶心，类似扫雷，没加边界控制，用了一堆try--------------------编程问答-------------------- --------------------编程问答-------------------- 没有看明白什么意思？ --------------------编程问答--------------------
public static void test(int[][] a, int i, int j)
{
try
{
if (a[i+1][j]==1)
{
a[i+1][j] = 2;
test(a, i+1, j);
}
}
catch (Exception e)
{}
try
{
if (a[i-1][j]==1)
{
a[i-1][j] = 2;
test(a, i-1, j);
}
}
catch (Exception e)
{
}
try
{
if (a[i+1][j+1]==1)
{
a[i+1][j+1] = 2;
test(a, i+1, j+1);
}
}
catch (Exception e)
{
}
try
{
if (a[i-1][j-1]==1)
{
a[i-1][j-1] = 2;
test(a, i-1, j-1);
}
}
catch (Exception e)
{
}
try
{
if (a[i+1][j-1]==1)
{
a[i+1][j-1] = 2;
test(a, i+1, j-1);
}
}
catch (Exception e)
{
}
try
{
if (a[i][j-1]==1)
{
a[i][j-1] = 2;
test(a, i+1, j-1);
}
}
catch (Exception e)
{
}
try
{
if (a[i][j+1]==1)
{
a[i][j+1] = 2;
test(a, i, j+1);
}
}
catch (Exception e)
{
}
try
{
if (a[i-1][j+1]==1)
{
a[i-1][j+1] = 2;
test(a, i-1, j+1);
}
}
catch (Exception e)
{
}
}
public static void main(String[] args) throws IOException, ParseException
{
int[][] a = {
{ 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 0, 1 },
{ 1, 1, 1, 1, 0, 0, 1 },
{ 1, 1, 0, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1 }
};
test(a, 0, 0);
boolean flag=true;
for (int[] temp : a)
{
String str=Arrays.toString(temp);
System.out.println(str);
if(str.indexOf("1")>0)
flag=false;
}
System.out.println(flag);
}
public class Demo1 {
static int a1[][] = {{1 ,1 ,1 ,1 ,1 ,1 ,1}
,{1 ,0, 0, 0, 0, 0, 1}
,{1 ,0, 1, 1, 1, 0, 1}
,{1 ,0, 1, 1, 1, 0, 1}
,{1 ,0, 1, 1, 1, 0, 1}
,{1 ,0 ,0 ,0 ,0 ,0, 1}
,{1 ,1, 1, 1, 1, 1, 1}};
static int m = a1.length;//最大长度
static int n = a1[0].length;//最大宽度
/**
* @param args
*/
public static void main(String[] args) {
Demo1 ha = new Demo1();
int[][] list = {{0,0}};
a1[0][0]=2;
// System.out.println(list3[0]);
ha.check(list);
boolean flag = true;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(a1[i][j]);
if(a1[i][j]==1)
{
flag = false;
}
}
System.out.println();
}
if(flag)
{
System.out.println("是开放的");
}
else
{
System.out.println("是闭合的");
}
}
/**
* 从第一点0,0开始，找他周围的8个点，
* 如果周围的8个点有1，则记录下来，
* 下次找这些1点的全部点，不断向外覆盖
* 被覆盖的1点往上加1，都变成2,0点不覆盖
* 当有一个点的周围8个点没有1存在时。
* 跳出循环，说明已经全部覆盖完了
* 最后循环矩阵，如果还存在1的点，
* 证明这个矩阵不是联通的，否则是联通的
* @param list
*/
public void check(int[][] list)
{
int[][] list1 = new int[100][];
int k=0;
for(int i=0;i<list.length;i++)
{
int[] zuobiao = list[i];
int x = zuobiao[0];//横坐标
int y = zuobiao[1];//纵坐标
/*
* 开始找周围8个点
* 的坐标
*/
int[][] eight = new int[8][2];//
//左上
if(x>0 && y>0)
{
eight[0][0] = x-1;
eight[0][1] = y-1;
if(a1[x-1][y-1] ==1)
{
a1[x-1][y-1] +=1;
list1[k] = eight[0];
k++;
}
}
//上
if(y>0)
{
eight[1][0] = x;
eight[1][1] = y-1;
if(a1[x][y-1] ==1)
{
a1[x][y-1] +=1;
list1[k] = eight[1];
k++;
}
}
//右上
if(x<m-1 && y>0)
{
eight[2][0] = x+1;
eight[2][1] = y-1;
if(a1[x+1][y-1] ==1)
{
a1[x+1][y-1] +=1;
list1[k] = eight[2];
k++;
}
}
//左
if(x>0)
{
eight[3][0] = x-1;
eight[3][1] = y;
if(a1[x-1][y] ==1)
{
a1[x-1][y] +=1;
list1[k] = eight[3];
k++;
}
}
//右
if(x<m-1)
{
eight[4][0] = x+1;
eight[4][1] = y;
if(a1[x+1][y] ==1)
{
a1[x+1][y] +=1;
list1[k] = eight[4];
k++;
}
}
//左下
if(x>0 && y<n-1)
{
eight[5][0] = x-1;
eight[5][1] = y+1;
if(a1[x-1][y+1] ==1)
{
a1[x-1][y+1] +=1;
list1[k] = eight[5];
k++;
}
}
//下
if(y<n-1)
{
eight[6][0] = x;
eight[6][1] = y+1;
if(a1[x][y+1] ==1)
{
a1[x][y+1] +=1;
list1[k] = eight[6];
k++;
}
}
//右下
if(x<m-1 && y<n-1)
{
eight[7][0] = x+1;
eight[7][1] = y+1;
if(a1[x+1][y+1] ==1)
{
a1[x+1][y+1] +=1;
list1[k] = eight[7];
k++;
}
}
}
//说明list1里没有点，说明覆盖完了
if(list1[0] == null)
{
return;
}else
{
int[][] list2 = null;
int i=0;
for(;i<list1.length;i++)
{
if(list1[i]==null)
{
list2 = new int[i][];
break;
}
}
for(int j=0;j<i;j++)
{
list2[j]= list1[j];
}
check(list2);
}
}
}
上边有我的思路说明，写完了，她说我太无聊了，伤心啊。
其实那8个点还可以整合一下的，条件都是差不多的，没爱弄。 --------------------编程问答-------------------- 晕，不让编辑 --------------------编程问答-------------------- 就是扫雷嘛
补充：Java , J2ME
