#!/bin/python3 import copy, sys # dirs in alpha order so that path comes out in lexical order dirs = {'E':(0,1), 'N':(-1,0), 'S':(1,0), 'W': (0,-1)} # set to false to print all solutions findone = True # set to true to print resulting grid for human verification printgrid = False ''' The first line contains $3$ integers $k$, $n$, and $m$, where $k$ is the length of the string, $n$ is the number of rows of the grid, and $m$ is the number of columns. Numbering begins with the upper-left cell. The second line describes a string of length $k$ consisting only of the characters \texttt{B}, \texttt{W}, and \texttt{\large .} (for black bead, white bead, and empty space). The first character will always be a \texttt{B} or \texttt{W}. The third line contains two integers $r$ and $c$, the row and column of the grid that contains the first bead in the string. ''' slen, rr, cc = [int(x) for x in input().strip().split()] beads = input().strip() start = [int(x)-1 for x in input().strip().split()] r,c = start def okloc(r,c): return r >= 0 and r < rr and c >= 0 and c < cc def copy_and_dfs(dir,r,c,path,grid,beads,bn): newr = r+dirs[dir][0] newc = c+dirs[dir][1] if not okloc(newr,newc): return False newgrid = grid #copy.deepcopy(grid) newgrid[r][c] = beads[bn] newpath = path[:] newpath.append(dir) return dfs(newr,newc,newpath,newgrid,beads,bn+1) def dfs(r,c,path,grid,beads,bn): #print(r,c,path) md = abs(r-start[0])+abs(c-start[1]) if md > (len(beads)-bn)+1: # too busy now to check exact bound return False ''' r,c is location we are about to fill with beads[bn] grid contains bead at each location ''' if bn == len(beads) and r == start[0] and c == start[1]: # have to check that the loop sews up correctly! if beads[-1] == 'B': # end on a black, next must be straight if path[-1] != path[0]: return False if beads[-1] == 'W': # end on a white, already straight there, but must have a turn if path[-3] == path[-2] == path[-1] == path[0]: return False if beads[0] == 'B': # come back to a black, must be a turn at 0 and straight at -1 if path[-2] != path[-1] or path[-1] == path[0]: return False if beads[0] == 'W': # come back to a white, must be straight at 0 and not straight on both sides if path[-1] != path[0] or path[-2] == path[-1] == path[0] == path[1]: return False if printgrid: for r in grid: print(r) print(path) if not findone: # have to print here since not returned up the stack print(''.join(path)) return path if bn == len(beads): # ends without connecting #print("didn't loop",r,c,start) return False if grid[r][c] != 'o': #print("crash", grid) return False # now figure out where is legal to go next if beads[bn] == '.': # what came before? if beads[bn-1] == 'W': for dir in dirs: if bn > 2 and path[-3] == path[-2] == path[-1] == dir: # was twice straight on the way in? then must turn continue res = copy_and_dfs(dir,r,c,path,grid,beads,bn) if res and findone: return res else: grid[r][c] = 'o' elif beads[bn-1] == 'B': # must continue straight, this dir == prev dir res = copy_and_dfs(path[-1],r,c,path,grid,beads,bn) if res and findone: return res else: grid[r][c] = 'o' else: # previous was also '.', do anything for dir in dirs: res = copy_and_dfs(dir,r,c,path,grid,beads,bn) if res and findone: return res else: grid[r][c] = 'o' elif beads[bn] == 'W': # placing a white, must be the same direction as coming in # but if previous was white, need to make sure it is OK if beads[bn-1] == 'W': if bn > 2 and path[-3] == path[-2] == path[-1]: return False res = copy_and_dfs(path[-1],r,c,path,grid,beads,bn) if res and findone: return res else: grid[r][c] = 'o' else: # 'B' # placing a black # if previous wasn't straight, already fail if bn >=2 and path[-2] != path[-1]: return False # otherwise, can't go straight (i.e. don't match path[-1]) for dir in dirs: if bn > 1 and path[-1] == dir: continue res = copy_and_dfs(dir,r,c,path,grid,beads,bn) if res and findone: return res else: grid[r][c] = 'o' return False # let's do the first step separately here # I mean, it seemed like a good idea to do so at the time... #print(beads,r,c) for dir in dirs: nextr = r+dirs[dir][0] nextc = c+dirs[dir][1] if okloc(nextr,nextc): path = [dir] grid = [['o' for _ in range(cc)] for _ in range(rr)] grid[r][c] = beads[0] res = dfs(nextr,nextc,path,grid,beads,1) if res: print(''.join(res)) if findone: sys.exit(0) print('impossible')