Weather Forecast
2007.08.23 12:51 ACM/ICPC 2003
[問題] 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
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |