Weather Forecast

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem D

[解説]

深さ優先探索。探索空間をいかに小さくするかがポイント。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<cassert>
003 using namespace std;
004 #define DMAX 370
005 #define SMAX 4096
006 #define SIZE 16
007 
008 static const int nextP[9+2][5] = {{0, 1, 2, 4, 8},
009                                  {0, 1, 2, 5, 9},
010                                  {0, 1, 2, 6, 10},
011                                  {-1, -1, -1, -1 -1},
012                                  {0, 4, 5, 6, 8},
013                                  {1, 4, 5, 6, 9},
014                                  {2, 4, 5, 6, 10},
015                                  {-1, -1, -1, -1 -1},
016                                  {0, 4, 8, 9, 10},
017                                  {1, 5, 8, 9, 10},
018                                  {2, 6, 8, 9, 10}};
019 
020 int nday;
021 int schedule[DMAX][SIZE];
022 int no_rainy[SIZE];
023 bool visited[DMAX][11][SMAX];
024 
025 bool checkFestival(int pos, int day ){
026     if ( schedule[day][pos + 0] == 1 ||
027         schedule[day][pos + 1] == 1 ||
028         schedule[day][pos + 4] == 1 ||
029         schedule[day][pos + 5] == 1 ) return true;
030     return false;
031 }
032 
033 bool check7NoRainy(){
034     for ( int i = 0; i < SIZE; i++ ){
035         if ( no_rainy[i] >= 7 ) return true;
036     }
037     return false;
038 }
039 
040 int getState(){
041     return no_rainy[0] + no_rainy[3]*8 + no_rainy[12]*64 + no_rainy[15]*512;
042 }
043 
044 bool recursive( int pos, int day ){
045     if ( day == nday ) return true;
046     visited[day][pos][getState()] = true;
047 
048     int tmp[SIZE];
049     for ( int i = 0; i < SIZE; i++ ) tmp[i] = no_rainy[i];
050 
051     for ( int n = 0; n < 5; n++ ){
052         if ( checkFestival( nextP[pos][n], day+1 ) ) continue;
053     
054         for ( int i = 0; i < SIZE; i++ ) no_rainy[i] = tmp[i];
055     
056         for ( int i = 0; i < SIZE; i++ ){
057             if ( i == pos || i == pos + 1 || i == pos + 4 || i == pos + 5 ) {
058                 no_rainy[i] = 0;
059             } else no_rainy[i]++;
060         }
061     
062         if ( check7NoRainy() ) continue;
063         if ( visited[day+1][nextP[pos][n]][getState()] ) continue;
064     
065         if ( recursive( nextP[pos][n], day+1 ) ) return true;
066     }
067 
068     return false;
069 }
070 
071 void compute(){
072     for ( int i = 0; i < SIZE; i++ ) no_rainy[i] = 0;
073     for ( int i = 0; i < DMAX; i++ ){
074         for (int  j = 0; j < 11; j++ ){
075             for ( int k = 0; k < SMAX; k++ ) visited[i][j][k] = false;
076         }
077     }
078 
079     if ( !checkFestival( 5, 0 ) && recursive( 5, 0 ) ) cout << 1 << endl;
080     else cout << 0 << endl;
081 }
082 
083 bool input(){
084     cin >> nday;
085     if ( nday == 0 ) return false;
086     for ( int i = 0; i < nday; i++ ){
087         for ( int j = 0; j < SIZE; j++ ) cin >> schedule[i][j];
088     }
089     for ( int j = 0; j < SIZE; j++ ) schedule[nday][j] = 0;
090 
091     return true;
092 }
093 
094 main(){
095     while ( input() ) compute();
096 }
097