emu in blogjava

public class SalesRouting {

public int howMany(String[] adj) {
int rowCount = adj.length;
int cellCount = adj[0].length();
int[] m = new int[cellCount];
//先看看Location0＆1有没有直接连同的，就是只通过一个Location就到
//等于2的就是可行的通道
for(int i=2; i<cellCount; i++){
if(adj[0].charAt(i) == '1')
m[i] += 1;
if(adj[1].charAt(i) == '1')
m[i] += 1;
}
//只搜索右上的三角，用m[]表示连通状态，现在m是Location0＆1的连通状态
//0表示同0＆1的不连通，1表示连通，2表示有通路。
//用m1表示剩下的Location的连通状态
for(int j=2; j<rowCount; j++){
//for(int k=0; k<rowCount; k++)
// System.out.print(m[k]+" ");
//System.out.println(" ");
//这里判断m[]==1非常重要，
//m[]==0就是集合不连通，m[]==2就是已经连通，不需要再判断了
if(m[j] == 1){
for(int i=j; i<cellCount; i++){
if((adj[j].charAt(i) == '1') && (m[i] != 2)){
m[i]++;
}
}
}
}

//计数
int result = 0;
for(int i=2; i<cellCount; i++){
if(m[i] == 2)
result++;
}

return result;
}

public static void main(String[] args) {
SalesRouting sr = new SalesRouting();

int result = sr.howMany(new String[]{"001","001","110"});
System.out.println(result);
result = sr.howMany(new String[]{"0010","0010","1100","0000"});
System.out.println(result);
result = sr.howMany(new String[]{"001100","000001","100010","100010","001101","010010"});
System.out.println(result);
result = sr.howMany(new String[]{"001111","001111","110000","110000","110000","110000"});
System.out.println(result);
result = sr.howMany(new String[]{"00000","00000","00000","00000","00000"});
System.out.println(result);
}
}   回复  更多评论
  

500合1000的还没做出来，
1000的我感觉好难，不知有谁已经成功了  回复  更多评论
  

500的用DP求出所有子串是否回文即可
1000的没做出来，不过看到有人直接用公式2^(a+b)+2^c次……汗
frog我倒是250的看不懂你的解法，这样肯定能保证最大么？  回复  更多评论
  

package salesRouting;

public class SalesRouting {

public static int howMany(String[] adj) {
matrix = new int[adj.length][adj[0].length()];
flags = new int[adj.length];

for(int i = 0; i < adj.length; i++) {
flags[i] = 0;
for(int j = 0; j < adj[0].length(); j++) {
matrix[i][j] = adj[i].charAt(j) - 48;

}
}

return iterate(0);
}

private static int[][] matrix;
private static int[] flags;
private static int iterate(int index) {
int result = 0;
if(index == 1) {
System.out.print(index+ " ");
return 1;
}

int next = 1;
while(next < matrix.length) {
if(matrix[index][next] == 1 && flags[next] == 0 && flags[index] == 0) {
if(index != 0 && index != 1) flags[index] = 1;
int success = iterate(next);
if (success == 1) {
if(index == 0) {
System.out.println(0 + " ");
} else System.out.print(index+ " ");
result++;
}else flags[index] = 0;
}
next++;
}
return result;
}
}



到底该怎么保证最大呢？ 我找了个例子：
String[] str={"001100","000011","100110","101001","011000","010100"};

想了半天没有想出来该怎么保证结果是最大。  回复  更多评论