Problem:
Grid There is a n × n grid D where each cell contains either 1 or 0. Your task is to create a program that takes the gird data as input and computes the greatest number of consecutive 1s in either vertical, horizontal, or diagonal direction. For example, the consecutive 1s with greatest number in the figure below is circled by the dashed-line.   The size of the grid n is an integer where 2 ≤ n ≤ 255. Input The input is a sequence of datasets. The end of the input is indicated by a line containing one zero. Each dataset is formatted as follows: n
D 11 D 12 ... D 1n D 21 D 22 ... D 2n .
  .
D n1 D n2 ... D nn  Output For each dataset, print the greatest number of consecutive 1s. Sample Input 5
00011
00101
01000
10101
00010
8
11000001
10110111
01100111
01111010
11111111
01011010
10100010
10000001
2
01
00
3
000
000
000
0 Output for the Sample Input 4
8
1
0

Solution (Python):
def f(x):
  a = 0
  b = 0
  for e in x:
    b = [0, b+1][e]
    a = max(a, b)
  return a
def d(M):
  n = len(M)
  X=[]
  for i in range(-n+1,n):
    x = [0]*n
    for j in range(n):
      if 0<=i+j<n: x[j] = M[j][i+j]
    X.append(x)
  return X

while 1:
  n = input()
  if n==0: break
  A = []
  B = []
  for _ in [0]*n:
    e = map(int, list(raw_input()))
    A.append(e)
    B.append(e[::-1])
  print max(map(f, A+zip(*A)+d(A)+d(B)))

Solution (Python):
def f(x):
  a = 0
  b = 0
  for e in x:
    b = [0, b+1][e]
    a = max(a, b)
  return a
def d(M):
  n = len(M)
  X=[]
  for i in range(-n+1,n):
    x = [0]*n
    for j in range(n):
      if 0<=i+j<n: x[j] = M[j][i+j]
    X.append(x)
  return X

while 1:
  n = input()
  if n==0: break
  A = [map(int, list(raw_input())) for _ in [0]*n]
  B = [e[::-1] for e in A]
  print max(map(f, A+zip(*A)+d(A)+d(B)))

Solution (Python):
def f():
    max_c = 0
    c = 0
    for h in range(n):
        for w in range(n):
            if grid[h][w] == 1:
                    c += 1
            else:
                if  max_c < c:
                    max_c = c
                c = 0
        else:
            if  max_c < c:
                max_c = c
            c = 0
    
    for w in range(n):
        for h in range(n):
            if grid[h][w] == 1:
                c += 1
            else:
                if  max_c < c:
                    max_c = c
                c = 0
        else:
            if  max_c < c:
                max_c = c
            c = 0
    
    for p in range(n):
        for a in range(n-p):
            if grid[p+a][0+a] == 1:
                c += 1
            else:
                if  max_c < c:
                    max_c = c
                c = 0
        else:
            if  max_c < c:
                max_c = c
            c = 0
        
    for p in range(1,n):
        for a in range(n-p):
            if grid[0+a][p+a] == 1:
                c += 1
            else:
                if  max_c < c:
                    max_c = c
                c = 0
        else:
            if  max_c < c:
                max_c = c
            c = 0
                
    for p in range(n):
        for a in range(n-p):
            if grid[p+a][n-1-a] == 1:
                c += 1
            else:
                if  max_c < c:
                    max_c = c
                c = 0
        else:
            if  max_c < c:
                max_c = c
            c = 0
            
    for p in range(n, -1, -1):
        for a in range(p):
            if grid[0+a][p-1-a] == 1:
                c += 1
            else:
                if  max_c < c:
                    max_c = c
                c = 0
        else:
            if  max_c < c:
                max_c = c
            c = 0
                
    print max_c
        
while True:
    n = input()
    if n == 0: break
    grid = [map(int, raw_input()) for i in range(n)]
    f()

Solution (Python):
while 1:
    n = int(input())
    if n == 0:
        break
    L = [input() for i in range(n)]
    ans = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if L[i][j] == '1':
                cnt += 1
            else:
                if ans < cnt:
                    ans = cnt
                cnt = 0
        if ans < cnt:
            ans = cnt
        cnt = 0
        for j in range(n):
            if L[j][i] == '1':
                cnt += 1
            else:
                if ans < cnt:
                    ans = cnt
                cnt = 0
        if ans < cnt:
            ans = cnt
    for i in range(n):
        cnt = 0
        for j in range(n-i):
            if L[i+j][j] == '1':
                cnt += 1
            else:
                if ans < cnt:
                    ans = cnt
                cnt = 0
        if ans < cnt:
            ans = cnt
        cnt = 0
        for j in range(n-i):
            if L[j][i+j] == '1':
                cnt += 1
            else:
                if ans < cnt:
                    ans = cnt
                cnt = 0
        if ans < cnt:
            ans = cnt
        cnt = 0
        for j in range(i+1):
            if L[i-j][j] == '1':
                cnt += 1
            else:
                if ans < cnt:
                    ans = cnt
                cnt = 0
        if ans < cnt:
            ans = cnt
        cnt = 0
        for j in range(n-i):
            if L[i+j][n-1-j] == '1':
                cnt += 1
            else:
                if ans < cnt:
                    ans = cnt
                cnt = 0
        if ans < cnt:
            ans = cnt
    print(ans)

Solution (Python):


import sys, math, os, bisect


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def grid_length(n, grid):
    L = 0
    for row in grid:
        L = max(L, max([len(_) for _ in row.split('0')]))
    for c in range(n):
        col = ''.join([grid[r][c] for r in range(n)])
        L = max(L, max([len(_) for _ in col.split('0')]))
    for row in range(-n, 2 * n):
        diag = ''.join([grid[row+c][c] for c in range(n) if 0 <= row + c < n])
        L = max(L, max([len(_) for _ in diag.split('0')]))
        diag = ''.join([grid[row-c][c] for c in range(n) if 0 <= row - c < n])
        L = max(L, max([len(_) for _ in diag.split('0')]))
    return L

while True:
    n = int(input())
    if n == 0:
        break
    grid = [input().strip() for _ in range(n)]
    print(grid_length(n, grid))

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0151&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [list(map(int, list(input().strip('\n')))) for _ in range(n)]

        if n == 1:              
            print(data[0][0])
            continue

        
        N = [[0] * n for _ in range(n)]
        W = [[0] * n for _ in range(n)]
        NW = [[0] * n for _ in range(n)]
        NE = [[0] * n for _ in range(n)]
        N_max = 0               
        W_max = 0
        NW_max = 0
        NE_max = 0

        for i in range(n):
            for j in range(n):
                c = data[i][j]  

                
                ni = i - 1
                if ni < 0:
                    N[i][j] = c
                    if N[i][j] > N_max:
                        N_max = N[i][j]
                else:
                    if c == 1:
                        N[i][j] = N[ni][j] + 1
                        if N[i][j] > N_max:
                            N_max = N[i][j]
                    else:
                        N[i][j] = 0

                
                nj = j - 1
                if nj < 0:
                    W[i][j] = c
                    if W[i][j] > W_max:
                        W_max = W[i][j]
                else:
                    if c == 1:
                        W[i][j] = W[i][nj] + 1
                        if W[i][j] > W_max:
                            W_max = W[i][j]
                    else:
                        W[i][j] = 0

                
                ni = i - 1
                nj = j - 1
                if ni < 0 or nj < 0:
                    NW[i][j] = c
                    if NW[i][j] > NW_max:
                        NW_max = NW[i][j]
                else:
                    if c == 1:
                        NW[i][j] = NW[ni][nj] + 1
                        if NW[i][j] > NW_max:
                            NW_max = NW[i][j]
                    else:
                        NW[i][j] = 0

                
                ni = i - 1
                nj = j + 1
                if ni < 0 or nj >= n:
                    NE[i][j] = c
                    if NE[i][j] > NE_max:
                        NE_max = NE[i][j]
                else:
                    if c == 1:
                        NE[i][j] = NE[ni][nj] + 1
                        if NE[i][j] > NE_max:
                            NE_max = NE[i][j]
                    else:
                        NE[i][j] = 0

        print(max(N_max, W_max, NW_max, NE_max))



if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0151&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [list(map(int, list(input().strip('\n')))) for _ in range(n)]

        
        N = [[0] * n for _ in range(n)]
        W = [[0] * n for _ in range(n)]
        NW = [[0] * n for _ in range(n)]
        NE = [[0] * n for _ in range(n)]
        N_max = 0               
        W_max = 0
        NW_max = 0
        NE_max = 0

        for i in range(n):
            for j in range(n):
                c = data[i][j]  

                
                ni = i - 1
                if ni < 0:
                    N[i][j] = c
                    if N[i][j] > N_max:
                        N_max = N[i][j]
                else:
                    if c == 1:
                        N[i][j] = N[ni][j] + 1
                        if N[i][j] > N_max:
                            N_max = N[i][j]
                    else:
                        N[i][j] = 0

                
                nj = j - 1
                if nj < 0:
                    W[i][j] = c
                    if W[i][j] > W_max:
                        W_max = W[i][j]
                else:
                    if c == 1:
                        W[i][j] = W[i][nj] + 1
                        if W[i][j] > W_max:
                            W_max = W[i][j]
                    else:
                        W[i][j] = 0

                
                ni = i - 1
                nj = j - 1
                if ni < 0 or nj < 0:
                    NW[i][j] = c
                    if NW[i][j] > NW_max:
                        NW_max = NW[i][j]
                else:
                    if c == 1:
                        NW[i][j] = NW[ni][nj] + 1
                        if NW[i][j] > NW_max:
                            NW_max = NW[i][j]
                    else:
                        NW[i][j] = 0

                
                ni = i - 1
                nj = j + 1
                if ni < 0 or nj >= n:
                    NE[i][j] = c
                    if NE[i][j] > NE_max:
                        NE_max = NE[i][j]
                else:
                    if c == 1:
                        NE[i][j] = NE[ni][nj] + 1
                        if NE[i][j] > NE_max:
                            NE_max = NE[i][j]
                    else:
                        NE[i][j] = 0

        print(max(N_max, W_max, NW_max, NE_max))



if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
def scanning_area(grid, length, point_list, stride_x, stride_y):
    area = [[0 for _ in range(length + 1)] for __ in range(length + 1)]
    max_length = 0

    for row, col in point_list:
        if grid[row][col] == "1":
            area[row + stride_y][col + stride_x] = area[row][col] + 1
            max_length = max(max_length, area[row + stride_y][col + stride_x])

    return max_length


def create_point_list(length):
    points = []

    for count, r in enumerate(range(length - 1, 0, -1), 1):
        row = r
        for col in range(0, count, 1):
            points.append((row, col))
            row += 1

    for index in range(0, length):
        points.append((index, index))

    for lp in range(1, length):
        row = 0
        for col in range(lp, length):
            points.append((row, col))
            row += 1

    return points


while True:

    length = int(input())

    if length == 0:
        break

    grid = [input() for _ in range(length)]

    point_list = [[row, col] for row in range(length) for col in range(length)]

    line_length1 = scanning_area(grid, length, point_list, 1, 0)
    line_length2 = scanning_area(grid, length, point_list, 0, 1)

    point_list = create_point_list(length)
    line_length3 = scanning_area(grid, length, point_list, 1, 1)
    point_list.reverse()
    line_length4 = scanning_area(grid, length, point_list, -1, 1)

    max_length = max(line_length1, line_length2, line_length3, line_length4)
    print(max_length)

Solution (Python):
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    mp = ["0" + input() + "0" for _ in range(n)]
    mp.insert(0, "0" * (n + 2))
    mp.append("0" * (n + 2))
    score = [[[0] * 4 for _ in range(n + 2)] for _ in range(n + 2)]
    max_score = 0
    for i in range(1, n + 1):
      for j in range(1, n + 1):
        if mp[i][j] == "1":
          score[i][j][0] = score[i - 1][j][0] + 1
          score[i][j][1] = score[i][j - 1][1] + 1
          score[i][j][2] = score[i - 1][j - 1][2] + 1
          score[i][j][3] = score[i - 1][j + 1][3] + 1
          max_score = max(max_score, score[i][j][0], score[i][j][1], score[i][j][2], score[i][j][3])
        else:
          for k in range(4):
            score[i][j][k] = 0
    print(max_score)

main()

Solution (Python):
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    
    mp = ["0" + input() + "0" for _ in range(n)]
    mp.insert(0, "0" * (n + 2))
    mp.append("0" * (n + 2))
    
    score = [[[0] * 4 for _ in range(n + 2)] for _ in range(n + 2)]
    max_score = 0
    for i in range(1, n + 1):
      for j in range(1, n + 1):
        if mp[i][j] == "1":
          score[i][j][0] = score[i - 1][j][0] + 1
          score[i][j][1] = score[i][j - 1][1] + 1
          score[i][j][2] = score[i - 1][j - 1][2] + 1
          score[i][j][3] = score[i - 1][j + 1][3] + 1
          max_score = max(max_score, score[i][j][0], score[i][j][1], score[i][j][2], score[i][j][3])
    
    print(max_score)

main()

Solution (Python):
while True:
    n=input()
    if n==0:break
    L=[map(int,list(raw_input())) for i in range(n)]
    Q=[[] for i in range(2*n-1)]
    for i in range(n):
        for j in range(n):
            Q[i+j].append((i,j))

    P=[[] for i in range(2*n-1)]
    for i in range(n):
        for j in range(n-1,-1,-1):
            P[(n-1)-i+j].append((i,j))

    maxInt=0
    for i in range(n):
        cnt=0
        for j in range(n):
            if L[i][j]==1:
                cnt+=1
            else:
                cnt=0
            maxInt=max(cnt,maxInt)
    for i in range(n):
        cnt=0
        for j in range(n):
            if L[j][i]==1:
                cnt+=1
            else:
                cnt=0
            maxInt=max(cnt,maxInt)
    for p in P:
        cnt=0
        for i,j in p:
            if L[i][j]==1:
                cnt+=1
            else:
                cnt=0
            maxInt=max(cnt,maxInt)
    for q in Q:
        cnt=0
        for i,j in q:
            if L[i][j]==1:
                cnt+=1
            else:
                cnt=0
            maxInt=max(cnt,maxInt)
    print maxInt

Solution (Python):
def ge(n):
    for i in xrange(n):
        yield [(i,j) for j in xrange(n)]
        yield [(j,i) for j in xrange(n)]
        yield [(j,i-j) for j in xrange(i+1)]
        yield [(n-1-i+j,n-1-j) for j in xrange(i+1)]
        yield [(j,n-1-i+j) for j in xrange(i+1)]
        yield [(n-1-i+j,j) for j in xrange(i+1)]

def f(L):
    ret,a = 0,0
    for i in L:
        if i == 0:
            ret = max(ret,a)
            a = 0
        else:
            a += 1
    return max(ret,a)

while True:
    n = input()
    if n == 0:
        break
    A = [map(int,list(raw_input())) for _ in xrange(n)]
    print max(map(f,[map(lambda (i,j): A[i][j], p) for p in ge(n)]))

Solution (Python):



while True:
    n = int(input())
    if n == 0:
        break
    
    table = [[0 for i in range(n)] for j in range(n)]
    for l in range(n):
        line = input()
        for m in range(n):
            table[l][m] = int(line[m])

    t = 0
    ans = 0
    for i in range(n):
        for j in range(n):
            if table[i][j] > 0:
                t += 1
            else:
                ans = max(t, ans)
                t = 0
        ans = max(t, ans)
        t = 0

    for i in range(n):
        for j in range(n):
            if table[j][i] > 0:
                t += 1
            else:
                ans = max(t, ans)
                t = 0
        ans = max(t, ans)
        t = 0

    for c in range(n):
        for j in range(c+1):
            if table[c-j][j] > 0:
                t += 1
            else:
                ans = max(t, ans)
                t = 0
        ans = max(t, ans)
        t = 0
        

    for c in range(n):
        for j in range(c+1):
            if table[n-1-(c-j)][n-1-j] > 0:
                t += 1
            else:
                ans = max(t, ans)
                t = 0
        ans = max(t, ans)
        t = 0


    for c in range(n):
        for j in range(c+1):
            if table[n-1-(c-j)][j] > 0:
                t += 1
            else:
                ans = max(t, ans)
                t = 0
        ans = max(t, ans)
        t = 0


    for c in range(n):
        for j in range(c+1):
            if table[c-j][n-1-j] > 0:
                t += 1
            else:
                ans = max(t, ans)
                t = 0
        ans = max(t, ans)
        t = 0

        
    print(ans)