Ruby

고등학교 수학 확률과 통계 순열, 최단거리 길의 수.(가로+세로)!/ (가로! * 세로!)

require 'matrix'

def cnt_shortest_path(tile)
  fact = ->n { (1..n).reduce(1, :*) }
  dist = ->pa,pb { pa.zip(pb).map {|a,b| (a-b).abs } }
  path = ->pa,pb { h,w = dist[pa, pb]; fact[w + h] / (fact[w] * fact[h]) }

  m = Matrix[*tile.split.map(&:chars)]
  a, s, b = %w(A S B).map {|i| m.index(i) }
  path[a, s] * path[s, b]
end

Test

tile_1 = "A000\n" +
         "0000\n" +
         "00S0\n" +
         "000B\n"
tile_2 = "A000\n" +
         "0SB0\n" +
         "0000\n"         
tile_3 = "S0000\n" +
         "00B00\n" +
         "0000A\n"         
expect( cnt_shortest_path(tile_1) ).to eq 12
expect( cnt_shortest_path(tile_2) ).to eq 2
expect( cnt_shortest_path(tile_3) ).to eq 45

Python으로 작성했습니다.

Input = [['A', 0, 0, 0],
         [0, 0, 0, 0],
         [0, 0, 'S', 0],
         [0, 0, 0, 'B']]

def factorial(num):
    fac = 1
    for n in range(1, num+1):
        fac *= n
    return(fac)

def ShortestDist(Input):
    # 0부터 index 시작하므로 -1
    n = len(Input)-1
    p = len(Input[0])-1

    for row in range(len(Input)):
        for column in range(len(Input[row])):
            if Input[row][column] == 'S':
                S_loc = [row, column]

    A_loc = [0, 0]
    B_loc = [n, p]

    a1 = S_loc[0] - A_loc[0]
    b1 = S_loc[0] - A_loc[0]
    First = factorial(a1 + b1) / (factorial(a1)*factorial(b1))

    a2 = B_loc[0] - S_loc[0]
    b2 = B_loc[0] - S_loc[0]
    Second = factorial(a2 + b2) / (factorial(a2)*factorial(b2))

    result = First * Second
    return(int(result))

ShortestDist(Input)

R로 작성했습니다.

Input <- matrix(c('A', '0', '0', '0',
                  '0', '0', '0', '0',
                  '0', '0', 'S', '0',
                  '0', '0', '0', 'B'), nrow = 4, byrow = TRUE)

ShortestDist <- function(Input){
  Loc <- data.frame(cbind(c(1, 1),
                          t(which(Input == 'S', arr.ind = TRUE)),
                          dim(Input)))
  colnames(Loc) <- c('A', 'S', 'B')
  first <- Loc$S - Loc$A
  first <- factorial(sum(first)) / (factorial(first[1])*factorial(first[2]))

  second <- Loc$B - Loc$S
  second <- factorial(sum(second)) / (factorial(second[1])*factorial(second[2]))

  result <- first*second
  return(result)
}

ShortestDist(Input)

import numpy as np

A,B,S = 1,1,1
T = [[A,0,0,0],[0,0,0,0],[0,0,S,0],[0,0,0,B]]
coord = []

def factorial(n):
    prod = 1
    for i in range(1,n+1):
        prod *= i
    return prod

for i in range(len(T)):
    for j in range(len(T[i])):
        if T[i][j] != 0:
            coord.append([i,j])
cnt = []
for i in range(len(coord)-1):
    cnt.append(np.subtract(coord[i+1],coord[i]))

prod = 1
for i in cnt:
    prod *= factorial(sum(i))/(factorial(i[0])*factorial(i[1]))
print(prod)

import java.math.*;

class Pos {
    public int x, y;

    public Pos() {}

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public Pos dist(Pos other) {
        return new Pos(Math.abs(this.x - other.x), Math.abs(this.y - other.y));
    }
}

public class test { 
    static int fact(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return n * fact(n - 1);
        }
    }

    static int routes(Pos P, Pos Q) {
        Pos d = P.dist(Q);
        return fact(d.x + d.y) / (fact(d.x) * fact(d.y));  
    }

    public static void main(String[] args) {
        int[][] map = new int[][] {{'A', '0', '0', '0'}, {'0', '0', '0', '0'}, {'0', '0', 'S', '0'}, {'0', '0', '0', 'B'}};
        int N = 4;
        Pos A = new Pos();
        Pos B = new Pos();
        Pos S = new Pos();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                switch (map[i][j]) {
                case 'A': A.x = i; A.y = j; break;
                case 'B': B.x = i; B.y = j; break;
                case 'S': S.x = i; S.y = j;
                }
            }
        }       
        System.out.println(routes(A, S) * routes(S, B));
    }
}

// golang 1.9
package main

import (
    "fmt"
    "math"
)

func main() {
    matrix := [][]string{
        {"A", "0", "0", "0"},
        {"0", "0", "0", "0"},
        {"0", "0", "S", "0"},
        {"0", "0", "0", "B"},
    }
    // matrx 내에서 A, S, B 위치 파악
    var ax, ay, sx, sy, bx, by float64
    for y := 0; y < len(matrix); y++ {
        for x := 0; x < len(matrix[y]); x++ {
            peekStr := matrix[y][x]
            switch peekStr {
            case "A":
                ax = float64(x)
                ay = float64(y)
            case "S":
                sx = float64(x)
                sy = float64(y)
            case "B":
                bx = float64(x)
                by = float64(y)
            }
        }
    }

    // 경로 수 구하는 함수
    // 동일한 것이 각각 p, q, r개로 이루어진 N개의 집합을 순서대로 나열하는 경우의 수는
    // N! / (p! * q! * r! * ...) where p+q+r+... = N
    // 이 문제의 경우 (x거리+y거리)! / {(x거리)!*(y거리)!}
    cases := func(dx float64, dy float64) float64 {
        return fact(dx+dy) / (fact(dx) * fact(dy))
    }

    // 경로 수 = (A->S 경로 수) * (S->B 경로 수)
    routes := cases(math.Abs(sx-ax), math.Abs(sy-ay)) *
        cases(math.Abs(bx-sx), math.Abs(by-sy))
    // 결과 출럭
    fmt.Println(routes)
}

// fact function
func fact(arg float64) float64 {
    if arg == 0 {
        return 1
    } else {
        return arg * fact(arg-1)
    }
}

// ans: 12

# python 3.6
from math import factorial

# 경로 수 구하는 함수
# 동일한 것이 각각 p, q, r개로 이루어진 N개의 집합을 순서대로 나열하는 경우의 수는
# N! / (p! * q! * r! * ...) where p + q + r + ... = N
# 이 문제의 경우(x거리 + y거리)! / {(x거리)!* (y거리)!}


def case(dx, dy):
    return factorial(abs(dx) + abs(dy)) / (factorial(abs(dx)) * factorial(abs(dy)))


# A, S, B 좌표 확인
inp = (("A", "0", "0", "0"),
       ("0", "0", "0", "0"),
       ("0", "0", "S", "0"),
       ("0", "0", "0", "B"))
for y, yv in enumerate(inp):
    for x, xv in enumerate(yv):
        if xv == "A":
            ax = x
            ay = y
        elif xv == "S":
            sx = x
            sy = y
        elif xv == "B":
            bx = x
            by = y

# A>S 경로 수 * S>B 경로 수
cases = int(case(sx - ax, sy - ay) * case(sx - bx, sy - by))
print(cases)  # ans: 12

import numpy as np
import itertools as iter
def facto(x):
    return np.array(range(1,x+1)).prod()
def method(x,y):
    return facto(abs(x)+abs(y))/(facto(abs(x))*facto(abs(y)))
def negative(x):
    return x<0

[A,B,S]=[1,1,1]
field=np.array([[A,0,0,0],[0,0,0,0],[0,0,S,0],[0,0,0,B]])                                   #출발지,목적지,경유지 설정한다.
Spoint=list(zip(*np.where(field==1)))                                                                   #출발지,목적지,경유지의 좌표를 구한다.
temp=np.array(list(iter.permutations(Spoint[1:-1])))                                          #경유지의 순열을 구한다.
dim=len(temp)                                                                                                             #순열의 갯수, 경유지 3개일 때 dim=3!=6
perm=np.zeros((dim,len(Spoint),2))                                                                       #좌표를 담을 3차원 행렬을 만든다.
perm[:,0],perm[:,1:-1],perm[:,-1]=Spoint[0],temp,Spoint[-1]                          #위에서 만든 행렬에 A,B,S의 좌표를 담는다.
perm[:,1:]=perm[:,1:]-perm[:,:-1]                                                                           #매 route의 cost를 구하기 위한 준비.
cost=[sum(filter(negative,x)) for x in perm.reshape(dim,(len(Spoint))*2)]     #cost계산
route=list(*np.where(np.array(cost)==max(cost)))                                              #'route'는 cost가 가장 작은 route의 index
num=0
for i in range(len(route)):
    num+=np.array([method(int(x),int(y)) for x,y in perm[route[i],:]]).prod()    #경우의 수 계산
print("모든 경유지를 지나 목적지에 도착하는 최단경로의 경우의 수는 %d가지이다." %int(num))   #출력

S의 수나 위치에 상관없이 모든 S를 지나면서 최단경로로 목적지에 도착하는 경우의 수를 구할 수 있습니다.

import itertools


route = [['S','0','0','0'],
         ['0','0','0','0'],
         ['S','0','A','0'],
         ['0','0','0','B']]


def findloc(char):
    res = []
    for y in range(len(route)):
        for x in range(len(route[y])):
            if route[y][x] == char:
                res.append([y,x])
    return res


def fact(n):
    fact = 1
    for i in range(1, n+1):
        fact *= i
    return fact


def ways(A, B):
    return fact(abs(A[0]-B[0]) + abs(A[1]-B[1])) // fact(abs(A[0]-B[0])) // fact(abs(A[1]-B[1]))


A = findloc('A')
B = findloc('B')
S = findloc('S')

shortest = [100000, '']

for items in itertools.permutations(S):
    path = A + list(items) + B
    cnt = 1
    for i in range(len(path)-1):
        cnt *= ways(path[i], path[i+1])
    if cnt < shortest[0]:
        shortest = cnt, path

print('cnt of shortest way : ', shortest[0])
print('shortest path : ', shortest[1])

수학을 다까먹어서.. 찾아보니 최단경로 찾는 공식이 있습니다.

(가로+ 세로)! / 가로! * 세로! 입니다.

#include<iostream>
using namespace std;

int main()
{
     int width;
     int height;
     char **arr; //2차원 배열
     int Ai = 0, Aj = 0;
     int Si = 0, Sj = 0;
     int Bi = 0, Bj = 0;
    //가로세로
     cout << "가로 입력 : "; cin >> width;
     cout << "세로 입력 : "; cin >> height;

 arr = new char*[height];

 for (int i = 0; i < height; i++)
 {
  arr[i] = new char[width];
 }
 for (int i = 0; i < width; i++)
 {
  for (int j = 0; j < height; j++)
  {
    cin >> arr[i][j];
  }
 }
 for (int i = 0; i < width; i++)
 {
  for (int j = 0; j < height; j++)
  {
   if (arr[i][j] == 'A')
   {
    Ai = i; Aj = j;
   }
   else if (arr[i][j] == 'S')
   {
    Si = i; Sj = j;
   }
   else if (arr[i][j] == 'B')
   {
    Bi = i; Bj = j;
   }
   //cout << arr[i][j];
  }
 }
 int Sheight = (Si - Ai); //A에서 S까지 세로
 int Swidth = (Sj - Aj); //A에서 S까지 가로
 int Bheight = (Bi - Si); //S에서 B까지 세로
 int Bwidth = (Bj - Sj); //S에서 B까지 가로

 int result = 1; //세로!
 int result2 = 1;// 가로!
 int result3 = 1; //가로+세로!
 int Firstroad; // A에서 S까지 가는 경우의 수
 int Secondroad; // S에서 B까지 가는 경우의 수
 // 공식 (가로 + 세로)! /(가로)! * (세로)! 

 for(int i = Sheight; i > 1; i--)
 {
    result *= i;
 }
 for(int i = Swidth; i > 1; i--)
 {
    result2 *= i;
 }
 for(int i = Swidth + Swidth; i > 1; i--)
 {
    result3 *= i;
 }

 Firstroad = result3 / (result * result2);

 result = 1; result2 = 1; result3 = 1;

 for(int i = Bheight; i > 1; i--)
 {
    result *= i;
 }
 for(int i = Bwidth; i > 1; i--)
 {
    result2 *= i;
 }
 for(int i = Bwidth + Bwidth; i > 1; i--)
 {
    result3 *= i;
 }
 Secondroad = result3 / (result * result2);
 cout << "최단 경로 경우의 수 : " << Firstroad*Secondroad << endl;
 return 0;
}

def fac(n):
    if n ==1 : return(1)
    return(fac(n-1)*n)

def hi(mapp):
    x1=0; y1=0
    x2=0; y2=0
    result =1
    for i in range(len(mapp)):
        for j in range(len(mapp[0])):
            if mapp[i][j] == 'a' : x1 = i; y1 =j
            if mapp[i][j] == 's' or mapp[i][j] == 'b' : 
                x2 = i; y2 =j
                result = result* fac((x2-x1)+(y2-y1))/fac(x2-x1)/fac(y2-y1)
                x1=x2; y1=y2
    return(int(result))

hi([['a',0,0,0],
        [0  ,0,0,0],
        [0, 0,'s',0],
        [0,  0,0,'b']])

최단경로수 = (a+b)!/a!b! 인걸 알아야 코딩할 수 있는 문제네요

abs_cor = lambda a: (abs(a[0][0]-a[1][0]), abs(a[0][1]-a[1][1]))
fac = lambda n: eval('(%s)'%('*'.join(str(x) for x in range(1, n+1)))) if n>0 else 1
f = lambda a, b: fac(a+b)//fac(a)//fac(b)
if __name__ == '__main__':
    s = 'A000\n0000\n00S0\n000B'.split('\n')
##    s = [*(input() for x in range(4))]
    li = [(),]*3
    a_s = s_b = (0,0)
    for y in range(len(s)):
        for x in range(len(s[y])):
            for i, c in enumerate(list('ASB')):
                if s[y][x] == c:
                    li[i] = (x,y)
    res = [*map(abs_cor, zip(li, li[1:]))]
    print(f(*res[0]) * f(*res[1]))

파이썬 3.6.2 64

파이썬 3.6

street ="""A000
0000
00S0
000B"""

def pointcheck(datalist):
# 시작점과 도착점을 넣어 출발점,경유지,도착지를 명시해준다.
    checkpoint = [[0,0]]
    for i, data in enumerate(datalist):
        for h, value in enumerate(data):
            if value == 'S':
                checkpoint.append([i,h])
    checkpoint.append([i,h])
    return checkpoint

def calcase(check):
# 시작점과 도착점을 설정하고 최단거리 경우의 수를 구한다.
# 경유지가 있을 경우 경유지를 기점으로 각각의 최단거리 경우의 수를 구한다.
    case,caselist,casetotal = 0,[],[]
    i_start,h_start = 0,0
    if t > 0:
        i_start,h_start = checkpoint[t-1][0],checkpoint[t-1][1]
    for i in range(i_start,check[0]+1):
        for h in range(h_start,check[1]+1):
            if i == i_start and h == h_start:
                pass
            elif i == i_start:
                case = 1
            elif h == h_start:
                case = 1
            else:
                if i > 0 and h > 0 and caselist:
                    case = casetotal[i - i_start -1][h - h_start]+ caselist[h - h_start -1]
            caselist.append(case)
        casetotal.append(caselist)
        caselist = []
    return casetotal[i-i_start][h-h_start]

if __name__ == "__main__":
    crosscase = 1
    datastring = street.split("\n")
    datalist = [list(i) for i in datastring]
    checkpoint = pointcheck(datalist)
    print("checkpoint =",checkpoint)
    for t,check in enumerate(checkpoint):
        if calcase(check) != 0:
            crosscase *= calcase(check)
    print("최단경로 경우의 수 :",crosscase)

*결과값

[[0, 0], [2, 2], [3, 3]]
12

# 파이썬


# 조합 함수를 준비한다.
def combinations(m, n):
    if m > n:
        return combinations(n, m)

    r = 1
    for t in range(n+1, m+n+1):
        r *= t
    for u in range(1, m+1):
        r /= u
    return r


# 지도는 리스트와 스트링으로 표시한다.
# 경유지는 최단 경로 내부에 있는 것으로 가정한다.
input_sample1 = ["a000",
                 "0000",
                 "00s0",
                 "000b"]

input_sample2 = []
while True:
    s1 = input("경로 입력: ")
    if s1:
        input_sample2.append(s1)
    else:
        break
for t in input_sample2:
    print(t)


# 경유지 좌표를 구한다.
# 경유지가 없으면 바로 조합을 시행한다.
# 경유지가 있으면 출발 - 경유지 - 도착점들의 좌표차로 조합 값을 구하고 구해진 조합 값들을 곱해 경우의 수를 구한다.
def short_course(input1):
    s = []
    for m, n in enumerate(input1):
        for u, v in enumerate(n):
            if v == "s":
                s.append((u+1, m+1))

    if not s:
        x = len(input1[0]-1)
        y = len(input1-1)
        return combinations(x, y)

    answer = 1
    s = [(1, 1)] + s + [(len(input1[0]), len(input1))]
    print(s)
    for t in range(len(s)-1):
        x = s[t+1][0] - s[t][0]
        y = s[t+1][1] - s[t][1]
        answer *= combinations(x, y)
        print(x, y, answer, combinations(x, y))
    return answer


print(short_course(input_sample1))
print(short_course(input_sample2))

def comb(n, m):
    def fac(a):
        if a == 1:
            return 1
        else:
            return a*fac(a-1)
    return int(fac(n)/(fac(m)*fac(n-m)))
def path(a):
    for i in range(len(a)):
        if a[i].count('A') == 1:
            place_A = (i, a[i].index('A'))
        if a[i].count('S') == 1:
            place_S= (i, a[i].index('S'))
        if a[i].count('B') == 1:
            place_B = (i, a[i].index('B'))
    return comb(abs(place_A[0] - place_S[0])+abs(place_A[1]-place_S[1]), abs(place_A[0] - place_S[0])) * comb(abs(place_S[0] - place_B[0])+abs(place_S[1]-place_B[1]), abs(place_S[0] - place_B[0]))


print(path([['A', 0, 0, 0],
            [0, 0, 0, 0],
            [0, 0, 'S', 0],
            [0, 0, 0, 'B']]))

S가 하나가 아닐 때, 최단경로를 모두 찾고 하나 이상일 경우 각 경우의 합을 구하는 알고리즘입니다. 반환값은 (최단거리, 최단경로의 수, 최단경로일때 경유지를 지나는 순서) 입니다.

def comb(n, m):
    def fac(a):
        if a == 1 or a == 0:
            return 1
        else:
            return a*fac(a-1)
    return int(fac(n)/(fac(m)*fac(n-m)))
def listshuffle(l):
    if len(l) == 1:
        return [l]
    else:
        result = list()
        a = [l[0]]
        l.pop(0)
        for i in listshuffle(l):
            for j in range(len(i)+1):
                result.append(i[:j]+a+i[j:])
        return result
def length(a):
    result = 0
    for i in range(len(a)-1):
        result += abs(a[i][0]-a[i+1][0]) + abs(a[i][1]-a[i+1][1])
    return result
def path(a):
    place_S = list()
    for i in range(len(a)):
        if a[i].count('A') == 1:
            place_A = (i, a[i].index('A'))
        if a[i].count('S') == 1:
            place_S.append((i, a[i].index('S')))
        if a[i].count('B') == 1:
            place_B = (i, a[i].index('B'))
    lengthset = list()
    shortpath = list()
    listS = listshuffle(place_S)
    for k in listS:
        lengthset.append(length([place_A]+k+[place_B]))
    m = min(lengthset)
    for k in listS:
        if length([place_A]+k+[place_B]) == m:
            shortpath.append(k)
    reesult = 0
    for i in shortpath:
        result = 1
        place = [place_A] + i + [place_B]
        for j in range(len(place)-1):
            result = result * comb(abs(place[j][0] - place[j+1][0])+abs(place[j][1]-place[j+1][1]), abs(place[j][0] - place[j+1][0]))
        reesult += result
    return m, reesult, shortpath


l = list()
while 1:
    a = input("공백으로 구분 :")
    if a == '':
        break
    else:
        l.append(a.split(' '))
print(path(l))

from itertools import permutations

def factorial(n):
    if n == 0: return 1
    return n*factorial(n-1)
# 최단루트 검색
def root_search(sp,ep,wp):
    rootall = tuple([sp]+[j for j in i]+[ep] for i in permutations(wp, len(wp)))
    rootlen = {}
    for i in rootall:
        rootlen[tuple(i)] = sum(abs(i[j][0]-i[j+1][0])+abs(i[j][1]-i[j+1][1]) for j in range(len(i)-1))
    return tuple(i for i in rootlen if rootlen[i] == min(rootlen.values()))
# 두 점의 경우의 수
def noc_root(f1,f2):
    w = abs(f1[0]-f2[0])
    h = abs(f1[1]-f2[1])
    return int(factorial(w+h)/(factorial(w)*factorial(h)))

# 맵 입력
mmm = '''\
A..........
..S........
...........
......S...B
...........
....S......
...........
...........
...........
........S..'''
# 좌표찾기
m = mmm.split('\n')
S = set()
for i in range(len(m)):
    for j in range(len(m[i])):
        if m[i][j] == 'A': A = (i,j)
        elif m[i][j] == 'B': B = (i,j)
        elif m[i][j] == 'S': S.add((i,j))
# 경우의 수 계산
noc = 0
print('지도 (경유지 수: {})\n\n{}\n\n최단 경로 좌표'.format(len(S),mmm))
for i in root_search(A,B,S):
    mul = 1
    for j in range(len(i)-1):
        mul *= noc_root(i[j],i[j+1])
    noc += mul
    print('{}'.format(i))
# 결과 출력
print('\n경우의 수: {}'.format(noc))

결과

지도 (경유지 수: 4)

A..........
..S........
...........
......S...B
...........
....S......
...........
...........
...........
........S..

최단 경로 좌표
((0, 0), (1, 2), (5, 4), (9, 8), (3, 6), (3, 10))
((0, 0), (1, 2), (5, 4), (3, 6), (9, 8), (3, 10))
((0, 0), (1, 2), (3, 6), (5, 4), (9, 8), (3, 10))

경우의 수: 829080

import math

matrix = []
while True:
    a =list(input())
    col = len(a)
    matrix.append(a)
    if a.count('B') == 1:
        break
row = len(matrix)

S_place = [[0, 0]]

for i in range(row):
    for j in range(col):
        if matrix[i][j] == 'S' or matrix[i][j] == 'B':
            S_place.append([i, j])

result = []

for i in range(len(S_place) - 1):
    x = abs(S_place[i + 1][0] - S_place[i][0])
    y = abs(S_place[i + 1][1] - S_place[i][1])
    result.append(math.factorial(x + y) // (math.factorial(x) * math.factorial(y)))

answer = 1

for i in result:
    answer *= i

print(answer)

import numpy as np

def factorial(num):
    fac=1
    for i in range (1, num+1):
        fac*=i
    return fac

#최단 경로의 경우의 수 공식
#아래로 간 횟수 :a, 오른쪽으로 간 횟수 :b
#(a+b)!/a!b!
def shortest_path(input_map):
    standard=["A","B","S"]
    location=[]
    distance=[]
    distance_case=1
    for i in range(0, len(input_map)):
        for j in range(0, len(input_map[i])):
            if input_map[i][j] in standard:
                location.append(i)
                location.append(j)
    k=3
    while k <len(location):
        distance_1 = abs(location[k-1]-location[k-3])
        distance_2 = abs(location[k]-location[k-2])
        distance.append(factorial(distance_1+distance_2)/(factorial(distance_1)*factorial(distance_2)))
        k+=2
    for p in distance:
        distance_case*=p

    return distance_case

import numpy as np
temp1 =[]
temp2 =[]
n = 1
Path = [[1,0,0,0],[0,0,0,0],[0,0,1,0],[0,0,0,1]]
def factorial(num):
    n = 1
    for i in range(1,num+1):
        n *= i
    return n

for i in range(len(Path)):
    for j in range(len(Path[i])):
        if Path[i][j] != 0:
            temp1.append([i,j])

for i in range(len(temp1)-1):
    temp2.append(np.subtract(temp1[i+1],temp1[i]))

for i in temp2:    

    n *= factorial(sum(i)) / (factorial(i[0])*factorial(i[1]))

print(n)

수학적으로 이해를 못해 앞의 문제 풀이를 참고 하였습니다.

from math import factorial

def path(road):
    for r in road:
        if 'A' in r:
            sRow = road.index(r)
            sCol = r.index('A')
        elif 'S' in r:
            pRow = road.index(r)
            pCol = r.index('S')
        elif 'B' in r:
            eRow = road.index(r)
            eCol = r.index('B')

    AtoS = factorial((pRow-sRow)+(pCol-sCol)) / (factorial(pRow-sRow) * factorial(pCol-sCol))
    StoB = factorial((eRow-pRow)+(eCol-pCol)) / (factorial(eRow-pRow) * factorial(eCol-pCol))

    return AtoS * StoB

if __name__ == '__main__':
    road = ['A000', '0000', '00S0', '000B']
    print('최단경로의 경우의 수: {}'.format(path(road)))

inp="A000\n0000\n00S0\n000B"
lst=[list(map(str,ln)) for ln in inp.split("\n")]
dx,dy=len(lst[0]),len(lst)
def fact(n):
    if n==1:
        return n
    return n*fact(n-1)

def path(p1,p2):
    return int(fact(abs(p1[0]-p2[0])+abs(p1[1]-p2[1]))/(fact(abs(p1[0]-p2[0]))*fact(abs(p1[1]-p2[1]))))

for x in range(dx):
    for y in range(dy):
        if lst[y][x]=="A":
            sp=(y,x)
        if lst[y][x]=="S":
            wp=(y,x)
        if lst[y][x]=="B":
            ep=(y,x)
print(path(sp,wp)*path(wp,ep))

def factorial(n):
    x = 1
    for i in range(n, 0, -1):
        x *= i
    return x


def minRoute(s):
    route = s.split("\n")
    for i in route:
        if 'S' in i:
            length = route.index(i)
            transverse = i.index('S')
    print(factorial(length+transverse)/(factorial(length)*factorial(transverse))*(factorial((len(route)-length)+(len(route[0])-transverse)-2)/(factorial((len(route)-length-1))*factorial(len(route[0])-transverse-1))))


minRoute("""A000
0000
00S0
000B""")

import math as m

def shorteset_path(path):

  starta=0

  startb=0

  answer=1

  for i in range(0,len(path),1):

    for j in range(0,len(path[i]),1):

      if path[i][j]=='s':

        patha=abs(starta-i)

        pathb=abs(startb-j)

        answer=answer*m.factorial(patha+pathb)/(m.factorial(patha)*m.factorial(pathb))

        starta=i

        startb=j

      elif path[i][j]=='b':

        patha=abs(starta-i)

        pathb=abs(startb-j)

        answer=answer*m.factorial(patha+pathb)/(m.factorial(patha)*m.factorial(pathb))

  return int(answer)

print(shorteset_path([['a',0,0,0],[0,0,0,0],[0,0,'s',0],[0,0,0,'b']]))

def factorial(num):
    result = 1
    for i in range(1,num+1):
        result *= i

    return result

def shortcut(_input):
    for i in range(len(_input)):
        for j in range(len(_input[i])):
            if _input[i][j] == 'A':
                idx_start = [i, j]
            if _input[i][j] == 'S':
                idx_middle = [i, j]
            if _input[i][j] == 'B':
                idx_final = [i, j]

    start_middle = factorial((idx_middle[0] - idx_start[0]) + (idx_middle[1] - idx_start[1])) / (factorial(idx_middle[0] - idx_start[0])*factorial(idx_middle[1] - idx_start[1]))
    middle_final = factorial((idx_final[0] - idx_middle[0]) + (idx_final[1] - idx_middle[1])) / (factorial(idx_final[0] - idx_middle[0])*factorial(idx_final[1] - idx_middle[1]))

    result = start_middle * middle_final

    return int(result)

if __name__ == '__main__':
    input_array = [['A', '0', '0', '0'], ['0', '0', '0', '0'], ['0', '0', 'S', '0'], ['0', '0', '0', 'B']]
    print(shortcut(input_array))

#codingdojing_shorted_path_re

'''
input:
A000
0000
00S0
000B
'''

def fac(a: int):        #a = 0 일때, 0! = 1이다.
    if a == 1 or a == 0:
        return 1
    else:
        return a*fac(a-1)

route = []
s_row = 0 
s_columm = 0 
B_row = -1
B_columm = 0

print('start')
while True:         #다른 방식으로는,, input을 저장해서.. 아예 리스트형식, 돌리면서 (x,y) 세트
    B_row += 1 #total row
    new_line = input()    

    if 'S' in new_line: #(2,2)
        s_row = B_row
        s_columm = new_line.find('S') 
    elif 'B' in new_line: # when end point is included.(3,2)
        B_columm = new_line.find('B')
        break
    else:
        pass

#절대값 필요. -가 나오는 경우도 고려.
path_1 = fac(abs(s_row+s_columm)) / (fac(abs(s_row))*fac(abs(s_columm))) 
path_2 = fac(abs((B_row+B_columm) - (s_row+s_columm))) / (fac(abs(B_row-s_row))*fac(abs(B_columm-s_columm)))

print(f'shortest path: {int(path_1*path_2)}')

r = int(input("행수를 입력하시오"))
c = int(input("열수를 입력하시오"))

arr = [[input() for k in range(c)] for i in range(r)]
pos=[]
for i in range(r):
    for k in range(c):
        if arr[i][k] =='A':
            pos.insert(0,[i,k])
        elif arr[i][k] =='S':
            pos.append([i,k])
        elif arr[i][k] =='B':
            posB=[i,k]
pos.append(posB)
print(pos)
dis=1
for k in range(len(pos)-1):
    if pos[k][0]==pos[k+1][0] or pos[k][1]==pos[k+1][1] :
        dis *= 1
    else:
        dis *= abs(pos[k+1][0]-pos[k][0])+abs(pos[k+1][1]-pos[k][1])

print(dis)

2차원 배열을 이용했어요 목적지 B만 따로 추출해서 pos배열의 끝에 append 해줬습니다

r = int(input("행수를 입력하시오"))
c = int(input("열수를 입력하시오"))

arr = [[input() for k in range(c)] for i in range(r)]
pos=[]
for i in range(r):
    for k in range(c):
        if arr[i][k] =='A':
            pos.insert(0,[i,k])
        elif arr[i][k] =='S':
            pos.append([i,k])
        elif arr[i][k] =='B':
            posB=[i,k]
pos.append(posB)
print(pos)
dis=1
for k in range(len(pos)-1):
    if pos[k][0]==pos[k+1][0] or pos[k][1]==pos[k+1][1] :
        dis *= 1
    else:
        dis *= abs(pos[k+1][0]-pos[k][0])+abs(pos[k+1][1]-pos[k][1])

print(dis)

2차원 배열을 이용했어요 목적지 B만 따로 추출해서 pos배열의 끝에 append 해줬습니다

// Rust

fn path() -> usize {

let road = "A000
0000
00S0
000B";

//A, S, B의 위치 저장 (A < S < B 가정)
let mut locations = vec![(0, 0)];
for (y, line) in road.lines().map(str::trim).enumerate() { // y 0~
    for (x, ch) in line.chars().enumerate() { // x 0~
        if ['S', 'A', 'B'].contains(&ch) { locations.push((x, y));}
    }
}
locations.sort_by_key(|w| w.0.min(w.1));

//각 경유지 간(마지막은 B) 이동할 수 있는 경우의 수 곱하기
let mut result = 1;
for k in 1..locations.len() {
    let i = locations[k].0 - locations[k-1].0;
    let j = locations[k].1 - locations[k-1].1;
    result *= shortest_path(i, j);
}
result

}

fn shortest_path(i: usize, j: usize) -> usize { // i 가로 거리, j 세로 거리

if i * j == 0 { return 1; }
shortest_path(i-1, j) + shortest_path(i, j-1)

}

[test]

fn t() {

assert_eq!(path(), 12);

}