zoom第一题 dfs+ hashmap
import java.util.*;
public class test {
static int sum = 0;
public static void main(String[] args) {
int[] visited = new int[5];
HashMap<Integer,List<Integer>> map = new HashMap<>();
map.put(0,new ArrayList<Integer>(Arrays.asList(2)));
map.put(3,new ArrayList<>(Arrays.asList(2,1,4)));
map.put(4,new ArrayList<>(Arrays.asList(3)));
map.put(1,new ArrayList<>(Arrays.asList(3)));
map.put(2,new ArrayList<>(Arrays.asList(0,3)));
String s = "RRRBB";
visited[0] = 1;
if(s.charAt(0)=='R'){
sum = 1;
dfs(0,map,s,1,visited);
}else{
sum = -1;
dfs(0,map,s,-1,visited);
}
System.out.println(sum);
}
public static void dfs(int c, HashMap<Integer,List<Integer>> map, String s, int cn, int[] visited){
List list = map.get(c);
visited[c] = 1;
for(int i=0;i<list.size();i++){
int q = (int)list.get(i);
if(visited[q]==1) continue;
visited[q] = 1;
if(s.charAt(q)=='R'){
cn ++;
sum = sum + cn;
dfs(q,map,s,cn,visited);
cn --;
}else{
cn--;
sum = sum + cn;
dfs(q,map,s,cn,visited);
cn ++;
}
}
}
}
安克创新 Anker公司福利 324人发布
