What step should I take to reduce time cost?

I have replace text concatenation from list appendence. It didn't work.

# 40 - Paths in the Grid
#   * input all map data into lst
#   * generate all movements
#   * convert movements to path
#   * check and count legal paths

from random import random

def main():

    n = int(input().split()[0])
    data = []
    for i in range(n):
        data.append(input().split())

    allMove = geneAllMov(data)

    allPath = geneAllPath(data,allMove)

    r = countLegalPath(allPath)

    print(r)

def countLegalPath(allPath):
    c = 0
    for path in allPath:
        if not "X" in path:
            c = c + 1
    return c

def geneAllPath(data,allMove):
    path = []
    for move in allMove:
        p = ["@"]
        x = 0
        y = 0
        for m in move:
            if m == "R":
                y = y + 1
            else:
                x = x + 1
            p.append(data[x][y])
        path.append(p)
    return path


def geneAllMov(data):
    r = len(data)
    c = len(data[0])
    move = []

    n = f(r+c-2,r-1)//f(r-1,r-1)
    while len(move)<n:
        tr = 0
        tc = 0
        m = []
        while len(m)<r+c-2:
            if random() < 0.5:
                if tc < c - 1:
                    m.append("R")
                    tc = tc + 1
            else:
                if tr < r - 1:
                    m.append("D")
                    tr = tr + 1
        if not m in move:
            move.append(m)
    return move

def f(a,b):
    res = 1
    for i in range(a,a-b,-1):
        res = res * i
    return res

if __name__ == "__main__":
    main()

Please do not post entire programs here in open threads; this can give too much away to others. Instead, everybody who has solved a particular problem can visit your unsuccessful solution under your profile. For this particular problem, a few observations:

• There shouldn't be any need for random() decisions.
• The problem asks for the number of paths, not the paths themselves. Do you really need to store all paths?
• This problem has the dynamic-programming tag and talks about this approach. Have a look at Dynamic Programming on wikipedia.