マス目

パソコン甲子園2007予選問題

問題04 マス目

概要

各要素が 0 または 1 である n × n （n < 256）の２次元配列が与えられ、上下、左右、または対角線方向に並んだ 1 の列のうち、長さが最大のものの長さを出力せよ。

例えば、以下のような入力に対しては、4 を出力する。

00011
00101
01000
10101

解法

動的計画法で解きます。
T[i][j][k] を G[i][j] から k 方向(k は右上、上、左上、左の４種類)に 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 }