0

我编写了一个函数来查找通过表的所有路径。

#'X' is a full cell, ' ' is an empty cell
test1 = ["  X  X XX ",
         " X   XX  X",
         " X X X   X",
         "     X X  ",
         "  X  X    "]

def numAllPercs(table, numStreams):
    indeksiInVrsticeSplittani = [map(lambda x,y:(x,y), sorted(range(0,len(table))*len(table[0])),range(0,len(table[0])) * len(table))[i:i+len(table[0])] for i in range(0,len(map(lambda x,y:(x,y), sorted(range(0,len(table))*len(table[0])),range(0,len(table[0])) * len(table))),len(table[0]))]

def Poti(tockaX,seznamPoti,table,vejitveniSeznam):
    if(tockaX[0]+1>=len(table) or table[tockaX[0]+1][tockaX[1]] == 'X') and (tockaX[1]+1>=len(table[0]) or table[tockaX[0]][tockaX[1]+1] == 'X') and (tockaX[1]-1<0 or table[tockaX[0]][tockaX[1]-1] == 'X') :
        return (seznamPoti if len(vejitveniSeznam)==0 else seznamPoti.append(vejitveniSeznam.pop()))

    if(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X') and (tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X') and (tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    elif(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X') and (tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    elif(tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X') and (tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    elif(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X') and (tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    if(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X'):
       seznamPoti.append(seznamPoti[len(seznamPoti)-1]+[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]]])
       Poti(indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]],seznamPoti,table[:indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]] + [table[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]][:indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][1]] + "X" + table[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]][indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][1]+1:]] + table[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]+1:],vejitveniSeznam)

    if(tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X'):
        seznamPoti.append(seznamPoti[len(seznamPoti)-1]+[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1]])
        Poti(indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1],seznamPoti,table[:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]] + [table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]][:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][1]] + "X" + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]][indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][1]+1:]] + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]+1:],vejitveniSeznam)

    if(tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X'):
       seznamPoti.append(seznamPoti[len(seznamPoti)-1]+[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1]])
       Poti(indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1],seznamPoti,table[:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]] + [table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]][:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][1]] + "X" + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]][indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][1]+1:]] + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]+1:],vejitveniSeznam)

    return seznamPoti

def resujem(table,seznami):
    vsePoti = filter(lambda x:x[-1][0]==len(table)-1,filter(lambda x:x[0][0]==0,reduce(lambda x,y:x+y,map(lambda x: Poti(x,[[x]],[table[0][:x[1]]+"X"+table[0][x[1]+1:]]+table[1:],[]),map(lambda x: (0,x), map(lambda x:x[1],filter(lambda x:x[0]==' ',map(lambda x,y: (x,y), map(lambda x: list(x), table)[0], range(0,len(table[0]))))))))))
    vsePoti.sort()

    def mojPresek(kombinacija):
        return (0 if len(set(reduce(lambda x,y:x+y,kombinacija))) != len(reduce(lambda x,y:x+y,kombinacija)) else 1)

    return (len(list(vsePoti for vsePoti,_ in itertools.groupby(vsePoti))) if (numStreams == 1) else  sum(map(lambda x:mojPresek(x),[list(x) for x in itertools.combinations(list(vsePoti for vsePoti,_ in itertools.groupby(vsePoti)), numStreams)])))

return (0 if numStreams <= 0 else
        0 if len(filter(lambda x: x == 'X'*len(table[0]),table)) != 0 else
        0 if numStreams >  len(map(lambda x:x[1],filter(lambda x:x[0]==' ',map(lambda x,y: (x,y), map(lambda x: list(x), table)[0], range(0,len(table[0])))))) else
        resujem(table,[]))

该函数的参数是：我们在其中搜索所有可能路径的表以及可以同时流过该表的流的数量。

该程序适用于流的值，但如果参数为 5 0-4，则返回内存异常。numStreams

这个问题有没有不需要我改变算法的解决方案？

4

1 回答 1

1

不，这种方式没有解决方案。改变你的算法。好吧，好吧，如果您添加足够的内存，也许会有，但确实如此。你可以改变算法。如果这是令人失望的消息，我表示哀悼。

于 2012-11-21T12:17:56.277 回答