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有沒有直接連同的，就是只通過一個(gè)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[]表示連通狀態(tài)，現(xiàn)在m是Location0＆1的連通狀態(tài)
//0表示同0＆1的不連通，1表示連通，2表示有通路。
//用m1表示剩下的Location的連通狀態(tài)
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就是已經(jīng)連通，不需要再判斷了
if(m[j] == 1){
for(int i=j; i<cellCount; i++){
if((adj[j].charAt(i) == '1') && (m[i] != 2)){
m[i]++;
}
}
}
}

//計(jì)數(shù)
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);
}
}   回復(fù)  更多評(píng)論
  

500合1000的還沒做出來，
1000的我感覺好難，不知有誰已經(jīng)成功了  回復(fù)  更多評(píng)論
  

500的用DP求出所有子串是否回文即可
1000的沒做出來，不過看到有人直接用公式2^(a+b)+2^c次……汗
frog我倒是250的看不懂你的解法，這樣肯定能保證最大么？  回復(fù)  更多評(píng)論
  

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;
}
}



到底該怎么保證最大呢？ 我找了個(gè)例子：
String[] str={"001100","000011","100110","101001","011000","010100"};

想了半天沒有想出來該怎么保證結(jié)果是最大。  回復(fù)  更多評(píng)論