マス目
2007.09.28 09:55 パソコン甲子園 2007
パソコン甲子園2007予選問題
問題04 マス目
概要
各要素が 0 または 1 である n × n (n < 256)の2次元配列が与えられ、上下、左右、または対角線方向に並んだ 1 の列のうち、長さが最大のものの長さを出力せよ。
例えば、以下のような入力に対しては、4 を出力する。
解法
動的計画法で解きます。
T[i][j][k] を G[i][j] から k 方向(k は右上、上、左上、左の4種類)に 1 が連続する数とします。
これを各列(j)を左から右、各行(i)を上から下という順番で計算していきます。
G[i][j] が 0 であれば、T[i][j][k] (k = 0, 1, 2, 3) は 0 となり、
G[i][j] が 1 であれば、
T[i][j][0] = T[i-1][j+1][0] + 1 (右上),
T[i][j][1] = T[i-1][j][1] + 1, (上)
T[i][j][2] = T[i-1][j-1][2] + 1 (左上),
T[i][j][3] = T[i][j-1][3] + 1 (左)
となります。
T の要素の最大値が答えとなります。
サンプルプログラム
問題04 マス目
概要
各要素が 0 または 1 である n × n (n < 256)の2次元配列が与えられ、上下、左右、または対角線方向に並んだ 1 の列のうち、長さが最大のものの長さを出力せよ。
例えば、以下のような入力に対しては、4 を出力する。
00011 00101 01000 10101
解法
動的計画法で解きます。
T[i][j][k] を G[i][j] から k 方向(k は右上、上、左上、左の4種類)に 1 が連続する数とします。
これを各列(j)を左から右、各行(i)を上から下という順番で計算していきます。
G[i][j] が 0 であれば、T[i][j][k] (k = 0, 1, 2, 3) は 0 となり、
G[i][j] が 1 であれば、
T[i][j][0] = T[i-1][j+1][0] + 1 (右上),
T[i][j][1] = T[i-1][j][1] + 1, (上)
T[i][j][2] = T[i-1][j-1][2] + 1 (左上),
T[i][j][3] = T[i][j-1][3] + 1 (左)
となります。
T の要素の最大値が答えとなります。
サンプルプログラム
001 #include<iostream> 002 #include<algorithm> 003 using namespace std; 004 #define MAX 255 005 006 int n; 007 char G[MAX+2][MAX+2]; 008 int T[MAX+2][MAX+2][4]; 009 010 void compute(){ 011 for ( int i = 0; i < n + 2; i++ ){ 012 for ( int j = 0; j < n + 2; j++ ){ 013 for ( int k = 0; k < 4; k++ ) T[i][j][k] = 0; 014 } 015 } 016 017 static const int di[4] = {-1, -1, -1, 0}; 018 static const int dj[4] = {1, 0, -1, -1}; 019 020 int maxv = 0; 021 022 for ( int i = 0; i <= n; i++ ){ 023 for ( int j = 0; j <= n; j++ ){ 024 if ( G[i][j] == '1' ){ 025 for ( int k = 0; k < 4; k++ ){ 026 T[i][j][k] = T[i+di[k]][j+dj[k]][k] + 1; 027 maxv = max( maxv, T[i][j][k] ); 028 } 029 } 030 } 031 } 032 033 cout << maxv << endl; 034 } 035 036 main(){ 037 while(cin >> n, n){ 038 for ( int i = 1; i <= n; i++ ){ 039 for ( int j = 1; j <= n; j++ ) cin >> G[i][j]; 040 } 041 compute(); 042 } 043 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |