Aizu Online Judge 0043 Puzzle

■0043 Puzzle

a[k]=数字kが出てきた回数とする．
a[k]++;とすると，これはkを付け加えた場合に相当する．
あとは，aが条件をみたすかを簡単な探索で解く．

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.  void run(){  
17.   for(; sc.hasNext();){  
18.    String s=sc.next();  
19.    int[] a=new int[10];  
20.    for(int i=0; i<s.length(); i++){  
21.     a[s.charAt(i)-'0']++;  
22.    }  
23.    solve(a);  
24.   }  
25.  }  
26.   
27.  void solve(int[] a){  
28.   LinkedList<Integer> list=new LinkedList<Integer>();  
29.   for(int i=1; i<=9; i++){  
30.    a[i]++;  
31.    if(satisfy(a.clone())){  
32.     list.add(i);  
33.    }  
34.    a[i]--;  
35.   }  
36.   for(int i=0; i<list.size(); i++){  
37.    print(list.get(i)+(i==list.size()-1?"\n":" "));  
38.   }  
39.   if(list.size()==0){  
40.    println("0");  
41.   }  
42.  }  
43.   
44.  boolean satisfy(int[] a){  
45.   if(!check(a)){  
46.    return false;  
47.   }  
48.   for(int i=1; i<=9; i++){  
49.    a[i]-=2;  
50.    if(rec(a, 0)){  
51.     return true;  
52.    }  
53.    a[i]+=2;  
54.   }  
55.   return false;  
56.  }  
57.   
58.  boolean rec(int[] a, int n){  
59.   if(!check(a)){  
60.    return false;  
61.   }  
62.   if(n==4){  
63.    return true;  
64.   }  
65.   for(int i=1; i<=9; i++){  
66.    a[i]-=3;  
67.    if(rec(a, n+1)){  
68.     return true;  
69.    }  
70.    a[i]+=3;  
71.   }  
72.   for(int i=1; i<=7; i++){  
73.    a[i]--;  
74.    a[i+1]--;  
75.    a[i+2]--;  
76.    if(rec(a, n+1)){  
77.     return true;  
78.    }  
79.    a[i]++;  
80.    a[i+1]++;  
81.    a[i+2]++;  
82.   }  
83.   return false;  
84.  }  
85.   
86.  boolean check(int[] a){  
87.   for(int e : a){  
88.    if(e<0||e>4){  
89.     return false;  
90.    }  
91.   }  
92.   return true;  
93.  }  
94.   
95.  void debug(Object... os){  
96.   System.err.println(Arrays.deepToString(os));  
97.  }  
98.   
99.  void print(String s){  
100.   System.out.print(s);  
101.  }  
102.   
103.  void println(String s){  
104.   System.out.println(s);  
105.  }  
106.   
107.  public static void main(String[] args){  
108.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
109.   new Main().run();  
110.  }  
111. }  

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;

 void run(){
  for(; sc.hasNext();){
   String s=sc.next();
   int[] a=new int[10];
   for(int i=0; i<s.length(); i++){
    a[s.charAt(i)-'0']++;
   }
   solve(a);
  }
 }

 void solve(int[] a){
  LinkedList<Integer> list=new LinkedList<Integer>();
  for(int i=1; i<=9; i++){
   a[i]++;
   if(satisfy(a.clone())){
    list.add(i);
   }
   a[i]--;
  }
  for(int i=0; i<list.size(); i++){
   print(list.get(i)+(i==list.size()-1?"\n":" "));
  }
  if(list.size()==0){
   println("0");
  }
 }

 boolean satisfy(int[] a){
  if(!check(a)){
   return false;
  }
  for(int i=1; i<=9; i++){
   a[i]-=2;
   if(rec(a, 0)){
    return true;
   }
   a[i]+=2;
  }
  return false;
 }

 boolean rec(int[] a, int n){
  if(!check(a)){
   return false;
  }
  if(n==4){
   return true;
  }
  for(int i=1; i<=9; i++){
   a[i]-=3;
   if(rec(a, n+1)){
    return true;
   }
   a[i]+=3;
  }
  for(int i=1; i<=7; i++){
   a[i]--;
   a[i+1]--;
   a[i+2]--;
   if(rec(a, n+1)){
    return true;
   }
   a[i]++;
   a[i+1]++;
   a[i+2]++;
  }
  return false;
 }

 boolean check(int[] a){
  for(int e : a){
   if(e<0||e>4){
    return false;
   }
  }
  return true;
 }

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