Read problems statements in Mandarin Chinese , Russian and Vietnamese as well. 

Tic-Tac-Toe used to be Chef's favourite game during his childhood. Reminiscing in his childhood memories, he decided to create his own "Tic-Tac-Toe", with rules being similar to the original Tic-Tac-Toe, other than the fact that it is played on an NxN board.

The game is played between two players taking turns. First player puts an 'X' in an empty cell of the board, then the second player puts an 'O' in some other free cell. If the first player has K continuous X's or the second player has K continuous O's in row, column or diagonal, then he wins.

Chef started playing this new "Tic-Tac-Toe" with his assistant, beginning as the first player himself (that is, Chef plays 'X's). Currently, the game is ongoign, and it's Chef's turn. However, he needs to leave soon to begin tonight's dinner preparations, and has time to play only one more move. If he can win in one move, output "YES", otherwise output "NO" (without quotes). It is guaranteed that no player has already completed the winning criterion before this turn, and that it's a valid "Tic-Tac-Toe" game.

------ Input ------ 

The first line of input contains one integer T denoting the number of testcases. First line of each testcase contains two integers N and K, next N lines contains N characters each. Each character is either an 'X' denoting that the first player used this cell, an 'O' meaning that the second player used this cell, or a '.' (a period) representing a free cell.

------ Output ------ 

For each testcase, output, in a single line, "YES" if Chef can win in one move, or "NO" otherwise.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$3 ≤ N ≤ 20$
$1 ≤ K ≤ N$

------ Subtasks ------ 

$Subtask 1:  K  = 1. Points - 10$
$Subtask 2:  N  =  K  = 3. Points - 30$
$Subtask 3: Original constraints. Points - 60$

----- Sample Input 1 ------ 
3
3 3
XOX
O.O
XOX
3 1
...
...
...
3 2
...
...
...
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
Test #1:
In first testcase, put 'X' in (2, 2), in second we can put 'X' in any cell and win. 

----- Sample Input 2 ------ 
1
4 4
XOXO
OX..
XO..
OXOX
----- Sample Output 2 ------ 
YES
----- explanation 2 ------ 
Test #2:
If you put an 'X' in (3, 3), there will be four 'X's on the main diagonal (1, 1) - (2, 2) - (3, 3) - (4, 4).

Difficulty: MEDIUM_HARD
Tags: Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
def load_board(N):
	board = [None] * N
	for i in range(N):
		board[i] = input()
	return board

def is_chef_winner(board, K):
	N = len(board)
	for row in range(N):
		for col in range(N):
			if board[row][col] == '.':
				h_num_X = 1
				i = col - 1
				while i >= 0 and board[row][i] == 'X':
					h_num_X += 1
					i -= 1
				i = col + 1
				while i < N and board[row][i] == 'X':
					h_num_X += 1
					i += 1
				v_num_X = 1
				i = row - 1
				while i >= 0 and board[i][col] == 'X':
					v_num_X += 1
					i -= 1
				i = row + 1
				while i < N and board[i][col] == 'X':
					v_num_X += 1
					i += 1
				d_num_X = 1
				i = row - 1
				j = col - 1
				while i >= 0 and j >= 0 and (board[i][j] == 'X'):
					d_num_X += 1
					i -= 1
					j -= 1
				i = row + 1
				j = col + 1
				while i < N and j < N and (board[i][j] == 'X'):
					d_num_X += 1
					i += 1
					j += 1
				ad_num_X = 1
				i = row - 1
				j = col + 1
				while i >= 0 and j < N and (board[i][j] == 'X'):
					ad_num_X += 1
					i -= 1
					j += 1
				i = row + 1
				j = col - 1
				while i < N and j >= 0 and (board[i][j] == 'X'):
					ad_num_X += 1
					i += 1
					j -= 1
				if h_num_X >= K or v_num_X >= K or d_num_X >= K or (ad_num_X >= K):
					return True
	return False
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	board = load_board(N)
	if is_chef_winner(board, K):
		print('YES')
	else:
		print('NO')


def exploreHorizontalRight(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		j += 1
		return exploreHorizontalRight(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			j += 1
			isfilled = 1
			return exploreHorizontalRight(a, i, j, n, k, visited, isfilled)

def exploreHorizontalLeft(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		j -= 1
		return exploreHorizontalLeft(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			j -= 1
			isfilled = 1
			return exploreHorizontalLeft(a, i, j, n, k, visited, isfilled)

def exploreVerticalUp(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		i -= 1
		return exploreVerticalUp(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			i -= 1
			isfilled = 1
			return exploreVerticalUp(a, i, j, n, k, visited, isfilled)

def exploreVerticalDown(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		i += 1
		return exploreVerticalDown(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			i += 1
			isfilled = 1
			return exploreVerticalDown(a, i, j, n, k, visited, isfilled)

def exploreNorthEast(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		i -= 1
		j += 1
		return exploreNorthEast(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			i -= 1
			j += 1
			isfilled = 1
			return exploreNorthEast(a, i, j, n, k, visited, isfilled)

def exploreNorthWest(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		i -= 1
		j -= 1
		return exploreNorthWest(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			i -= 1
			j -= 1
			isfilled = 1
			return exploreNorthWest(a, i, j, n, k, visited, isfilled)

def exploreSouthEast(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		i += 1
		j += 1
		return exploreSouthEast(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			i += 1
			j += 1
			isfilled = 1
			return exploreSouthEast(a, i, j, n, k, visited, isfilled)

def exploreSouthWest(a, i, j, n, k, visited, isfilled):
	if visited == k:
		return 1
	if a[i][j] == 'O':
		return 0
	if a[i][j] == 'X':
		visited += 1
		i += 1
		j -= 1
		return exploreSouthWest(a, i, j, n, k, visited, isfilled)
	if a[i][j] == '.':
		if isfilled == 1:
			return 0
		else:
			visited += 1
			i += 1
			j -= 1
			isfilled = 1
			return exploreSouthWest(a, i, j, n, k, visited, isfilled)

def check(a, i, j, n, k, visited, isfilled):
	result = 0
	if k == 1:
		return 1
	else:
		if n >= k + j:
			result += exploreHorizontalRight(a, i, j + 1, n, k, visited, isfilled)
		if j + 1 >= k:
			result += exploreHorizontalLeft(a, i, j - 1, n, k, visited, isfilled)
		if n >= k + i:
			result += exploreVerticalDown(a, i + 1, j, n, k, visited, isfilled)
		if i + 1 >= k:
			result += exploreVerticalUp(a, i - 1, j, n, k, visited, isfilled)
		if n >= k + j and i + 1 >= k:
			result += exploreNorthEast(a, i - 1, j + 1, n, k, visited, isfilled)
		if n >= k + j and n >= k + i:
			result += exploreSouthEast(a, i + 1, j + 1, n, k, visited, isfilled)
		if j + 1 >= k and n >= k + i:
			result += exploreSouthWest(a, i + 1, j - 1, n, k, visited, isfilled)
		if j + 1 >= k and i + 1 >= k:
			result += exploreNorthWest(a, i - 1, j - 1, n, k, visited, isfilled)
	if result > 0:
		return 1
	else:
		return 0
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split(' ')))
	board = []
	for i in range(n):
		board.append(input())
	result = 0
	for i in range(n):
		for j in range(n):
			if board[i][j] == 'X':
				result = check(board, i, j, n, k, 1, 0)
			elif board[i][j] == '.':
				result = check(board, i, j, n, k, 1, 1)
			if result == 1:
				print('YES')
				break
		if result == 1:
			break
	if result == 0:
		print('NO')


from sys import stdin
T = int(stdin.readline().strip())
while T > 0:
	[N, K] = [int(n) for n in stdin.readline().strip().split()]
	grid1 = [0] * N
	for i in range(0, N):
		grid1[i] = list(stdin.readline().strip())
	try:
		for i in range(0, N):
			for j in range(0, N):
				if grid1[i][j] == '.':
					count = 1
					(checkI, checkJ) = (i - 1, j - 1)
					while checkI >= 0 and checkJ >= 0 and (grid1[checkI][checkJ] == 'X') and (count < K):
						count += 1
						checkI -= 1
						checkJ -= 1
					(checkI, checkJ) = (i + 1, j + 1)
					while checkI < N and checkJ < N and (grid1[checkI][checkJ] == 'X') and (count < K):
						count += 1
						checkI += 1
						checkJ += 1
					if count == K:
						raise Exception
						someFlag = True
						break
					count = 1
					(checkI, checkJ) = (i - 1, j + 1)
					while checkI >= 0 and checkJ < N and (grid1[checkI][checkJ] == 'X') and (count < K):
						count += 1
						checkI -= 1
						checkJ += 1
					(checkI, checkJ) = (i + 1, j - 1)
					while checkI < N and checkJ >= 0 and (grid1[checkI][checkJ] == 'X') and (count < K):
						count += 1
						checkI += 1
						checkJ -= 1
					if count == K:
						raise Exception
						someFlag = True
						break
					count = 1
					checkI = i - 1
					while checkI >= 0 and grid1[checkI][j] == 'X' and (count < K):
						count += 1
						checkI -= 1
					checkI = i + 1
					while checkI < N and grid1[checkI][j] == 'X' and (count < K):
						count += 1
						checkI += 1
					if count == K:
						raise Exception
						someFlag = True
						break
					count = 1
					checkJ = j - 1
					while checkJ >= 0 and grid1[i][checkJ] == 'X' and (count < K):
						count += 1
						checkJ -= 1
					checkJ = j + 1
					while checkJ < N and grid1[i][checkJ] == 'X' and (count < K):
						count += 1
						checkJ += 1
					if count == K:
						raise Exception
						someFlag = True
						break
	except Exception:
		print('YES')
	else:
		print('NO')
	T -= 1


T = int(input())
ops = []
for prog in range(0, T):
	(N, K) = map(int, input().split())
	field = []
	p1 = [1, 0, -1, 0]
	p2 = [0, -1, 0, 1]
	d1 = [1, -1, -1, 1]
	d2 = [-1, -1, 1, 1]
	for a in range(0, N):
		field.append(list(input()))

	def isFree(a, b):
		if a >= 0 and a < N:
			if b >= 0 and b < N:
				return True
			else:
				return False
		else:
			return False

	def check(a, b):
		done = False
		zbroj1 = 0
		zbroj2 = 0
		for p in range(0, 3, 2):
			for c in range(1, K):
				if isFree(a + c * p1[p], b + c * p2[p]) == True:
					if field[a + c * p1[p]][b + c * p2[p]] != 'X':
						break
					else:
						zbroj1 += 1
				else:
					break
		if zbroj1 + 1 >= K:
			done = True
		for p in range(1, 4, 2):
			for c in range(1, K):
				if isFree(a + c * p1[p], b + c * p2[p]) == True:
					if field[a + c * p1[p]][b + c * p2[p]] != 'X':
						break
					else:
						zbroj2 += 1
				else:
					break
		if zbroj2 + 1 >= K:
			done = True
		if done == False:
			zbroj1 = 0
			zbroj2 = 0
			for p in range(0, 3, 2):
				for c in range(1, K):
					if isFree(a + c * d1[p], b + c * d2[p]) == True:
						if field[a + c * d1[p]][b + c * d2[p]] != 'X':
							break
						else:
							zbroj1 += 1
					else:
						break
			if zbroj1 + 1 >= K:
				done = True
			for p in range(1, 4, 2):
				for c in range(1, K):
					if isFree(a + c * d1[p], b + c * d2[p]) == True:
						if field[a + c * d1[p]][b + c * d2[p]] != 'X':
							break
						else:
							zbroj2 += 1
					else:
						break
			if zbroj2 + 1 >= K:
				done = True
		return done

	def isGood(a, b):
		if field[a][b] == '.':
			return True
		else:
			return False
	op = False
	for a in range(0, N):
		for b in range(0, N):
			if isGood(a, b) == True:
				if check(a, b) == True:
					op = True
					break
	if op == False:
		ops.append('NO')
	else:
		ops.append('YES')
for o in ops:
	print(o)