Statement
The statement for this problem can be found in the Google CodeJam 2010 page, or click this link
Solution
The solution is quite straightforward: load, rotate, apply gravity and verify. Nothing really exciting.
I do the first two things at once, I load the matrix rotated. In order to accomplish that you have to notice that each row is going to be a column and that the first row becomes the last column, the second column becomes the column n-1, etc. Knowing that it's pretty obvious how I do that.
As gravity is applied per column, meaning that one column doesn't affect the effect of gravity in other column I apply it as soon as I finished loading a column. The algorithm is quite simple: I process each position from bottom to top and while there's a point I shift the string from top to bottom filling with useless characters.
And for searching I just brute-force on each row, column and diagonal(in both directions) line to see if blue or red have achieved K characters together. And based in those findings I return 'Both', 'Blue', 'Red' or 'Neither'.
The python source code (GCJ2010-1A-A.py):
def solve(): n, K = map(int, input().split(' ')) board = [['.' for i in range(n)] for j in range(n)] for i in range(n-1, -1, -1): # Load column n-i-1 line = input() for j in range(n): board[j][i] = line[j] # Apply gravity in that column for j in range(n-1, -1, -1): while board[j][i] == '.': for k in range(j, 0, -1): board[k][i] = board[k-1][i] board[0][i] = '#' blue = False red = False # Check for Vertical and horizontal for i in range(n): s = ''.join(board[i]) if 'B' * K in s: blue = True if 'R' * K in s: red = True s = ''.join(board[j][i] for j in range(n)) if 'B' * K in s: blue = True if 'R' * K in s: red = True # Check for Diagonal Right-Down and Left-Down for i in range(n): j = 0 s = ''.join(board[i+d][j+d] for d in range(n-i)) if 'B' * K in s: blue = True if 'R' * K in s: red = True s = ''.join(board[j+d][i+d] for d in range(n-i)) if 'B' * K in s: blue = True if 'R' * K in s: red = True s = ''.join(board[j+d][i-d] for d in range(i+1)) if 'B' * K in s: blue = True if 'R' * K in s: red = True s = ''.join(board[i+d][n-d-1] for d in range(n-i)) if 'B' * K in s: blue = True if 'R' * K in s: red = True if blue and red: return 'Both' if blue: return 'Blue' if red: return 'Red' return 'Neither' if __name__ == '__main__': t = int(input()) for case in range(1, t+1): print("Case #{0}: {1}".format(case, solve()))