for ICPC 21-22 prob 4

lonerook.py

import sys
import math

(r, c) = [int(x) for x in input().split(' ')]
'''
states:
0 -> empty
1-> knight
2-> attacked by knight
3 -> goal (target)
'''
EMPTY = 0
KNIGHT = 1
ATTACKED = 2
TARGET = 3
ROOK = 4

G = []

ur = 0
uc = 0
sr = 0
sc = 0
for line in sys.stdin:
    row = []
    for _c in line.rstrip():
        uc = 0
        to_add = EMPTY
        if _c == 'K':
            to_add = KNIGHT
        elif _c == 'T':
            to_add = TARGET
        elif _c == 'R':
            to_add = ROOK
            sr = ur
            sc = uc
        row.append(to_add)
        uc += 1
    ur += 1
    G.append(row)

knight_moves = [[-2, -1], [-2, 1], [2, -1], [2, 1],\
                [-1, 2], [-1, -2], [1, 2], [1, -2]]

def check_bounds(_i, _j, move):
    (u, v) = move
    ni = _i + u
    nj = _j + v
    if ni > r-1 or ni < 0: return False
    if nj > c-1 or nj < 0: return False
    return True

# what is attacked?
for i in range(r):
    for j in range(c):
        if G[i][j] != KNIGHT: continue
        for move in knight_moves:
            if not check_bounds(i, j, move): continue
            #if G[i+move[0]][j+move[1]] != EMPTY: continue
            G[i+move[0]][j+move[1]] = ATTACKED

# get available moves in col
def get_column_moves(rr, rc):
    moves = []
    # start at top and count down
    for i in range(r):
        if G[i][rc] == ROOK: continue
        if G[i][rc] == EMPTY: moves.append([i, rc])
        if G[i][rc] == KNIGHT:
            if i < rr: 
                moves = [[i, rc]]
            else:
                moves.append([i, rc])
                break
        if G[i][rc] == ATTACKED: continue
        if G[i][rc] == TARGET: moves.append([i,rc])
    return moves

def get_row_moves(rr, rc):
    moves = []
    # start at top and count down
    for j in range(c):
        if G[rr][j] == ROOK: continue
        elif G[rr][j] == EMPTY: moves.append([rr, j])
        elif G[rr][j] == KNIGHT:
            if j > rc: 
                moves.append([rr, j])
                break
            else:
                moves = [[rr, j]]
        elif G[rr][j] == ATTACKED: continue
        elif G[rr][j] == TARGET: moves.append([rr, j])
    return moves

# bfs

Q = [[sr, sc]]
vis = set()

go = True
while len(Q):
    if not go: break
    f = Q.pop()
    vis.add(tuple(f))
    (cr, cc) = f
    col_moves = get_column_moves(cr, cc)
    row_moves = get_row_moves(cr, cc)
    all_moves = col_moves + row_moves
    for npos in all_moves:
        if tuple(npos) in vis: continue
        if G[npos[0]][npos[1]] == TARGET:
            print('yes')
            go = False
        Q.insert(0, npos)

if go:
    print('no')