GCJ2010 - 1A - A - Rotate

# 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):
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[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()))
```