AOJ 0151: Grid

Grid | Aizu Online Judge

実装が面倒なやるだけっぽいですが、DPで書くとさくっと解けました。

遷移

左から、左上から、上から、右上からの4パターン。

状態の持ち方

dp[i][j][0] = i 行目 j 列目まで見た時、横向きにいくつ連続しているか
dp[i][j][1] = i 行目 j 列目まで見た時、縦向きにいくつ連続しているか
dp[i][j][2] = i 行目 j 列目まで見た時、右ななめ下向きにいくつ連続しているか
dp[i][j][3] = i 行目 j 列目まで見た時、左ななめ下向きにいくつ連続しているか

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back

int n;
int main(){
    int n;
    while(cin>>n&&n){
        int dp[256][256][4];
        rep(i,256)rep(j,256)rep(k,4)dp[i][j][k] = 0;

        vector<string> data(n);
        rep(i,n)cin>>data[i];
        
        int maxi = 0;
        rep(i,n){
            rep(j,n){
                if(data[i][j]=='1'){
                    dp[i][j][0] = ( j-1>=0          )*dp[i  ][j-1][0] +1;
                    dp[i][j][1] = ( i-1>=0          )*dp[i-1][j  ][1] +1;
                    dp[i][j][2] = ( i-1>=0&&j-1>=0  )*dp[i-1][j-1][2] +1;
                    dp[i][j][3] = ( i-1>=0&&j+1<n   )*dp[i-1][j+1][3] +1;

                    rep(k,4) maxi = max(maxi,dp[i][j][k]);
                }
            }
        }
        cout<<maxi<<endl;
    }
}