Aizu Online Judge 0179 Mysterious Worm

■0179 Mysterious Worm

深さ優先探索．同じ状態が何度も発生しないように，既に出た状態を集合に突っ込んでおくと良い(ただし，計算量がO(logn)であるものを用いないとTLEの可能性有)．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  String worm;  
17.   
18.  void run(){  
19.   for(;;){  
20.    worm=sc.next();  
21.    if(worm.equals("0")){  
22.     break;  
23.    }  
24.    solve();  
25.   }  
26.  }  
27.   
28.  void solve(){  
29.   LinkedList<String> que=new LinkedList<String>();  
30.   TreeSet<String> set=new TreeSet<String>();  
31.   HashMap<String, Integer> map=new HashMap<String, Integer>();  
32.   que.add(worm);  
33.   set.add(worm);  
34.   map.put(worm, 0);  
35.   for(; !que.isEmpty();){  
36.    String s=que.poll();  
37.    boolean f=true;  
38.    for(int i=0; i<s.length(); i++){  
39.     f&=s.charAt(0)==s.charAt(i);  
40.    }  
41.    if(f){  
42.     println(""+map.get(s));  
43.     return;  
44.    }  
45.    for(String t : next(s)){  
46.     if(!set.contains(t)){  
47.      que.offer(t);  
48.      set.add(t);  
49.      map.put(t, map.get(s)+1);  
50.     }  
51.    }  
52.   }  
53.   println("NA");  
54.  }  
55.   
56.  LinkedList<String> next(String s){  
57.   LinkedList<String> list=new LinkedList<String>();  
58.   for(int i=0; i<s.length()-1; i++){  
59.    if(s.charAt(i)!=s.charAt(i+1)){  
60.     char c='*';  
61.     switch(s.charAt(i)+s.charAt(i+1)){  
62.     case 'r'+'g':  
63.      c='b';  
64.      break;  
65.     case 'g'+'b':  
66.      c='r';  
67.      break;  
68.     case 'b'+'r':  
69.      c='g';  
70.      break;  
71.     }  
72.     list.add(s.substring(0, i)+c+c  
73.       +(i<s.length()-2?s.substring(i+2, s.length()):""));  
74.    }  
75.   }  
76.   return list;  
77.  }  
78.   
79.  void debug(Object... os){  
80.   System.err.println(Arrays.deepToString(os));  
81.  }  
82.   
83.  void print(String s){  
84.   System.out.print(s);  
85.  }  
86.   
87.  void println(String s){  
88.   System.out.println(s);  
89.  }  
90.   
91.  public static void main(String[] args){  
92.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
93.   new Main().run();  
94.  }  
95. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 String worm;

 void run(){
  for(;;){
   worm=sc.next();
   if(worm.equals("0")){
    break;
   }
   solve();
  }
 }

 void solve(){
  LinkedList<String> que=new LinkedList<String>();
  TreeSet<String> set=new TreeSet<String>();
  HashMap<String, Integer> map=new HashMap<String, Integer>();
  que.add(worm);
  set.add(worm);
  map.put(worm, 0);
  for(; !que.isEmpty();){
   String s=que.poll();
   boolean f=true;
   for(int i=0; i<s.length(); i++){
    f&=s.charAt(0)==s.charAt(i);
   }
   if(f){
    println(""+map.get(s));
    return;
   }
   for(String t : next(s)){
    if(!set.contains(t)){
     que.offer(t);
     set.add(t);
     map.put(t, map.get(s)+1);
    }
   }
  }
  println("NA");
 }

 LinkedList<String> next(String s){
  LinkedList<String> list=new LinkedList<String>();
  for(int i=0; i<s.length()-1; i++){
   if(s.charAt(i)!=s.charAt(i+1)){
    char c='*';
    switch(s.charAt(i)+s.charAt(i+1)){
    case 'r'+'g':
     c='b';
     break;
    case 'g'+'b':
     c='r';
     break;
    case 'b'+'r':
     c='g';
     break;
    }
    list.add(s.substring(0, i)+c+c
      +(i<s.length()-2?s.substring(i+2, s.length()):""));
   }
  }
  return list;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}