input과 같은 체스판이 있다.
나이트의 시작 위치는 'K'(5,0)이다.
나이트는 직진 한번 + 대각 한번으로 이동한다.
나이트를 'CEREBRUM' 이라는 문자 순서대로 이동하시오.
(3가지 경로가 존재함)
input:
RERSCM
ECRUCU
UBBSBV
BCCRRR
RVCERE
KSEVEU
output:
[(3, 1), (4, 3), (3, 5), (4, 3), (2, 2), (3, 4), (1, 3), (0, 5)]
[(3, 1), (1, 0), (0, 2), (1, 0), (2, 2), (3, 4), (1, 3), (0, 5)]
[(4, 2), (5, 4), (3, 5), (4, 3), (2, 2), (3, 4), (1, 3), (0, 5)]
5개의 풀이가 있습니다.
dr = [(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (-1,2), (1,-2), (-1,-2)]
wp = 'CEREBRUM'
test = '''\
RERSCM
ECRUCU
UBBSBV
BCCRRR
RVCERE
KSEVEU'''
brd = test.splitlines()
def roots(*p):
ret = []
for i in p:
for dx, dy in dr:
x, y = i[-1]
if 0 <= x+dx < 6 and 0 <= y+dy < 6 and brd[x+dx][y+dy] == wp[len(i)-1]:
ret.append(i+[((x+dx), (y+dy))])
if ret == [] or len(ret[0]) == len(wp)+1: return ret
return roots(*ret)
iloc = [(5,0)]
for i in roots(iloc): print(i)
def knight(x, y, stops, path):
global brd, X, Y
if not stops:
print(path)
else:
directions = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
for xx, yy in [(x + dx, y + dy) for dx, dy in directions]:
if 0 <= xx < X and 0 <= yy < Y and brd[xx][yy] == stops[0]:
knight(xx, yy, stops[1:], path + [(xx, yy)])
brd = '''RERSCM
ECRUCU
UBBSBV
BCCRRR
RVCERE
KSEVEU'''.splitlines()
X, Y = len(brd), len(brd[0])
knight(5, 0, list('CEREBRUM'), [])
board = [["R","E","R","S","C","M"],["E","C","R","U","C","U"],["U","B","B","S","B","V"],["B","C","C","R","R","R"],["R","V","C","E","R","E"],["K","S","E","V","E","U"]]
movelist = [(-2,-1),(-1,-2),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2)]
word = "CEREBRUM"
result = [[(5,0)]]
step = 0
temp = []
while step < len(word):
for move in movelist:
for route in result:
if route[-1][0]+move[0] in range(6) and route[-1][1]+move[1] in range(6) and board[route[-1][0]+move[0]][route[-1][1]+move[1]] == word[step]:
temp.append(route+[(route[-1][0]+move[0],route[-1][1]+move[1])])
step += 1
result = temp
temp = []
for fin in result:
print(fin[1:])
inp="""RERSCM
ECRUCU
UBBSBV
BCCRRR
RVCERE
KSEVEU"""
lst=[list(map(str,ln)) for ln in inp.split("\n")]
route=[(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (-1,2), (1,-2), (-1,-2)]
wrd="CEREBRUM"
n=0
elst=[]
def KM(x,y,wrd,elst):
if not wrd:
print(elst)
else:
for dx,dy in route:
if 0<=x+dx<6 and 0<=y+dy<6 and lst[x+dx][y+dy]==wrd[0]:
KM(x+dx,y+dy,wrd[1:],elst+[(x+dx,y+dy)])
KM(5,0,wrd,elst)
using System;
using System.Collections.Generic;
namespace solution
{
class Program
{
public static string[] map;
public static string alphabeticalOrder;
static void Main(string[] args)
{
map = new string[6]
{ "RERSCM", "ECRUCU","UBBSBV","BCCRRR","RVCERE","KSEVEU"};
alphabeticalOrder = "CEREBRUM";
List<List<string>> root = new List<List<string>>();
moveK(5, 0, 0, new List<string>(), root);
Console.WriteLine("\n\n output:");
foreach (var ll in root)
{
Console.WriteLine("[{0}]", string.Join(", ", ll));
}
}
private static void moveK(int r, int c, int idx, List<string> list, List<List<string>> root)
{
if(idx == alphabeticalOrder.Length)
{
root.Add(new List<string>(list));
return;
}
int[] dr = { -2, -2, -1, 1, 2, 2, 1, -1 };
int[] dc = { -1, 1, 2, 2, 1, -1, -2, -2 };
for (int i = 0; i < 8; i++)
{
int R = r + dr[i];
int C = c + dc[i];
if(R>=0 && C>=0 && R<6 && C<6 && map[R][C] == alphabeticalOrder[idx])
{
list.Add("(" + R + ", " + C + ")");
moveK(R, C, idx + 1, list, root);
list.RemoveAt(list.Count - 1);
}
}
}
}
}