2044 Weather Forecast

「2044 Weather Forecast」の編集履歴（バックアップ）一覧に戻る

2044 Weather Forecast - (2006/04/17 (月) 02:07:13) のソース

**2044 Weather Forecast
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
**解答方針
探索問題のテクニックが詰まっている良問．

一日目の雲の位置はわかっているので，その状態を根としたDFSを行う．雲を動かせる位置の候補は必ず5ヶ所（南北方向に動かすのが2通り，東西方向が2通り，不動が1通り）なので，1つの状態から5つの子状態が生まれるが，「雲の覆うマスでその日にイベントがある」「7日間連続して雲に覆われないマスがある」のどちらかが成り立つ場合は当然カットする．さらに計算時間短縮のために「すでに探索した状態」をカットすることは必須となる．

さて，DFSの単位となる「状態」をどうやって定義するかであるが，「現在の日付」「現在の雲の位置」「各マスの連続日照日数」さえわかればよい．ここで，連続日照日数は0,4,11,15の四隅だけ覚えておけばよいことに注意．0に雨が降るとき1,4,5にも必ず雨が降るので，0の周辺3マスの連続日照日数が0の連続日照日数を超えることは決してなく，他の隅についても同様だからである．

Javaで解く場合はStackとHashSetを使うことになるが，HashSetを正しく利用するためにはequals,hashCodeを上書きする必要がある．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             if(n==0) break;
             boolean[][] schedule = new boolean[n][16];
             for(int i=0;i<n;i++){
                 for(int j=0;j<16;j++){
                     int s = sc.nextInt();
                     if(s==1) schedule[i][j] = true;
                     else schedule[i][j] = false;
                 }
             }
             Solver sol = new Solver(n,schedule);
             System.out.println(sol.solve());
         }
     }
 }
 
 class Solver{
     int n;
     boolean[][] schedule;
     Solver(int n, boolean[][] schedule) {
         this.n = n;
         this.schedule = schedule;
     }
     public int solve(){
         
         Stack<State> st = new Stack<State>();
         HashSet<State> h = new HashSet<State>();
         
         // initial state
         State init = new State();
         if(valid(init)){
             if(end(init)){
                 return 1;
             }
             else{
                 st.push(init);
                 h.add(init);
             }
         }
         
         // DFS
         while(!st.empty()){
             State s = st.pop();
             
             for(int i=0;i<5;i++){
                 State next = s.move(i);
                 if(valid(next)&&!h.contains(next)){
                     if(end(next)){
                         return 1;
                     }
                     else{
                         st.push(next);
                         h.add(next);
                     }
                 }
             }
         }
         
         return 0;
     }
     private boolean valid(State s){    
         int d = s.day;
         boolean[] sch = schedule[d];
         int x = s.cloud%3;
         int y = s.cloud/3;
         if(sch[4*y+x]||sch[4*y+x+1]||sch[4*y+x+4]||sch[4*y+x+5]) return false;
         
         for(int i=0;i<4;i++) if(s.dry[i]>=7) return false;
         
         return true;
     }
     private boolean end(State s){
         if(n-1==s.day) return true;
         else return false;
     }
 }
 
 class State{
     int day;
     int cloud;
     int dry[];
     State(){
         day = 0;
         cloud = 4;
         dry = new int[4];
         for(int i=0;i<4;i++) dry[i] = 1;
     }
     State(State s){
         this.day = s.day;
         this.cloud = s.cloud;
         this.dry = new int[4];
         for(int i=0;i<4;i++) this.dry[i] = s.dry[i];
     }
     public State move(int dir){
         State ret = new State(this);
         ret.day++;
         
         int x = ret.cloud%3;
         int y = ret.cloud/3;
         // dir=0,1 N-S direction
         if(dir==0) y = (y+1)%3;
         else if(dir==1) y = (y+2)%3;
         // dir=2,3 E-W direction
         else if(dir==2) x = (x+1)%3;
         else if(dir==3) x = (x+2)%3;
         // dir=4 no move
         
         ret.cloud = y*3+x;
         
         for(int i=0;i<4;i++) ret.dry[i]++;
         ret.rain();
         return ret;
     }
     private void rain(){
         if(cloud==0) dry[0] = 0;
         else if(cloud==2) dry[1] = 0;
         else if(cloud==6) dry[2] = 0;
         else if(cloud==8) dry[3] = 0;
     }
     public boolean equals(Object o){
         State s = (State)o;
         if(this.day!=s.day||this.cloud!=s.cloud) return false;
         for(int i=0;i<4;i++) if(this.dry[i]!=s.dry[i]) return false;
         return true;
     }
     public int hashCode(){
         int ret = day<<20+cloud<<16;
         for(int i=0;i<4;i++) ret += dry[i]<<(4*i);
         return ret;
     }
 }