Problem:
Problem B: Cleaning Robot Dr. Asimov, a robotics researcher, loves to research, but hates houseworks and his house were really dirty. So, he has developed a cleaning robot. As shown in the following figure, his house has 9 rooms, where each room is identified by an alphabet:   The robot he developed operates as follows:  If the battery runs down, the robot stops.  If not so, the robot chooses a direction from four cardinal points with the equal probability, and moves to the room in that direction. Then, the robot clean the room and consumes 1 point of the battery.  However, if there is no room in that direction, the robot does not move and remains the same room. In addition, there is a junk room in the house where the robot can not enter, and the robot also remains when it tries to enter the junk room. The robot also consumes 1 point of the battery when it remains the same place.  A battery charger for the robot is in a room. It would be convenient for Dr. Asimov if the robot stops at the battery room when its battery run down. Your task is to write a program which computes the probability of the robot stopping at the battery room. Input The input consists of several datasets. Each dataset consists of:  n  s t b   n is an integer that indicates the initial battery point. s , t , b are alphabets respectively represent the room where the robot is initially, the battery room, and the junk room. The input ends with a dataset which consists of single 0 for n . Your program should not output for this dataset. Output For each dataset, print the probability as a floating point number in a line. The answer may not have an error greater than 0.000001. Constraints  Judge data includes at most 100 data sets.  n ≤ 15  s , t , b are distinct.  Sample Input 1
E A C
1
E B C
2
E A B
0 Output for the Sample Input 0.00000000
0.25000000
0.06250000

Solution (Python):



mv = ((-1,0),(0,1),(1,0),(0,-1))
while True:
	n = int(input())
	if n == 0: break
	t1, t2, t3 = input().split()
	s, t, b = ord(t1)-ord('A'), ord(t2)-ord('A'), ord(t3)-ord('A')
	f = [[[0.0 for a in range(3)] for c in range(3)] for r in range(17)]
	f[0][s//3][s%3] = 1
	for j in range(1, n+1):
		for r in range(3):
			for c in range(3):
				for i in range(4):
					r2, c2 = r + mv[i][0], c + mv[i][1]
					if r2 < 0 or r2 >= 3 or c2 < 0 or c2 >= 3 or 3*r2+c2 == b:
						r2, c2 = r, c
					f[j][r2][c2] += f[j-1][r][c]/4
	print(f[n][t//3][t%3])

Solution (Python):
time = -1
place = ["a","b","c","d","e","f","g","h","i"]
empty_count={}
for i in place:
	empty_count[i] = 0
count_d = empty_count.copy()	

def reset():
	global d
	global count_d
	d={"a":["a","a","b","d"],"b":["a","e","c","b"],"c":["b","f","c","c"],"d":["a","e","g","d"],"e":["b","d","f","h"],"f":["c","e","i","f"],"g":["d","h","g","g"],"h":["g","e","i","h"],"i":["f","h","i","i"]}
	count_d = empty_count.copy()
	
	
def pre_set(start_place,fix_place):
	global d
	global count_d
	for i in place:
		d[i] = list(("").join(d[i]).replace(fix_place,i))
	count_d[start_place] = 1
	
def repeat(time):
	global count_d
	for i in range (time):
		new_count_d = empty_count.copy()
		old_count_d = count_d.copy()
		for j in place:
			for k in d[j]:
				new_count_d[k] += old_count_d[j]
		count_d = new_count_d.copy() 

while time != 0:
	time = int(raw_input())
	if time == 0:
		break
	else:
		info_pre = raw_input().split()
		info = []
		for i in info_pre:
			info.append(i.lower())
		
	reset()
	pre_set(info[0],info[2])
	repeat(time)
	print (count_d[info[1]])/float((4**time))

Solution (Python):
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        [s,t,b]=raw_input().split()
        rm='ABCDEFGHI'
        nxt={}
        A={}
        B={}
        nxt["A"]='AABD'
        nxt["B"]='ABEC'
        nxt["C"]='CCBF'
        nxt["D"]='ADEG'
        nxt["E"]='BDHF'
        nxt["F"]='CEFI'
        nxt["G"]='GGDH'
        nxt["H"]='GHEI'
        nxt["I"]='IIHF'
        for r in rm:
            A[r]=0
            B[r]=0
        A[s]=1
        for i in range(n):
            for r in rm:
                B[r]=0
            for r in rm:
                for c in nxt[r]:
                    if c==b:
                        B[r]+= A[r]*0.25
                    else:
                        B[c]+= A[r]*0.25
            A=B.copy()
        print A[t]

Solution (Python):


import os
import sys
import itertools

f = sys.stdin
d = {'A': (0,0), 'B': (0,1), 'C': (0,2),
     'D': (1,0), 'E': (1,1), 'F': (1,2),
     'G': (2,0), 'H': (2,1), 'I': (2,2)}

while True:
    n = int(f.readline().strip())
    if n==0: sys.exit()

    s,t,b = f.readline().split()

    dp = [dict([((j,k),0) for k in xrange(3) for j in xrange(3)]) for i in xrange(n+1)]
    dp[0][d[t]] = 1

    for i in xrange(1,n+1):
        for j in xrange(3):
            for k in xrange(3):
                
                x,y = max(0,j-1), k
                if d[b]==(x,y):
                    dp[i][(j,k)] += dp[i-1][(j,k)]
                else:
                    dp[i][(x,y)] += dp[i-1][(j,k)]

                
                x,y = min(j+1,2), k
                if d[b]==(x,y):
                    dp[i][(j,k)] += dp[i-1][(j,k)]
                else:
                    dp[i][(x,y)] += dp[i-1][(j,k)]

                
                x,y = j, max(0,k-1)
                if d[b]==(x,y):
                    dp[i][(j,k)] += dp[i-1][(j,k)]
                else:
                    dp[i][(x,y)] += dp[i-1][(j,k)]

                
                x,y = j, min(2, k+1)
                if d[b]==(x,y):
                    dp[i][(j,k)] += dp[i-1][(j,k)]
                else:
                    dp[i][(x,y)] += dp[i-1][(j,k)]

    print dp[n][d[s]]/4.**n

Solution (Python):
x = []
for y in range(9):
        x += [[chr(65+y),y]]
Room = dict(x)

By = [[0,0,1,3],[0,1,2,4],[1,2,2,5],[0,3,4,6],[1,3,5,7]]
By += [[2,4,5,8],[3,6,6,7],[4,6,7,8],[5,7,8,8]]

while 1:
        BatP = input()
        if BatP == 0:
                break
        Info = raw_input().split()
        Prob = [0 for x in range(9)]
        Prob[Room[Info[0]]] = 1

        while 0 < BatP:
                BatP -= 1
                AftI = Prob[:]
                Prob = [0 for x in range(9)]

                for x in range(9):
                        if x == Room[Info[2]]:
                                for y in range(4):
                                        Prob[By[x][y]] += AftI[By[x][y]] *0.25
                        else:
                                for y in range(4):
                                        Prob[x] += AftI[By[x][y]] * 0.25

        print('{:.8f}'.format(Prob[Room[Info[1]]]))

Solution (Python):
dic = {"A":(0,0), "B":(0,1), "C":(0,2),
       "D":(1,0), "E":(1,1), "F":(1,2),
       "G":(2,0), "H":(2,1), "I":(2,2)}
while True:
    n = input()
    if n == 0:
        break
    dp = [[[0] * 3 for _ in xrange(3)] for _ in xrange(n + 1)]
    s, t, b = raw_input().split()
    dp[0][dic[s][0]][dic[s][1]] = 1
    for i in xrange(n):
        for y in xrange(3):
            for x in xrange(3):
                for dx, dy in ((0, 1), (-1, 0), (0, -1), (1, 0)):
                    if not(0 <= x + dx < 3 and 0 <= y + dy < 3) or dic[b] == (y + dy, x + dx):
                        dp[i + 1][y][x] += dp[i][y][x]
                    else:
                        dp[i + 1][y + dy][x + dx] += dp[i][y][x]
    print "{:.8f}".format(float(dp[n][dic[t][0]][dic[t][1]]) / 4.**n)

Solution (Python):
index = "ABCDEFGHI".index
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
while 1:
    N = int(input())
    if N == 0:
        break
    s, t, b = map(index, input().split())
    S = [[0]*3 for i in range(3)]
    sy, sx = divmod(s, 3)
    ty, tx = divmod(t, 3)
    by, bx = divmod(b, 3)
    T = [[0]*3 for i in range(3)]
    S[sy][sx] = 1
    for i in range(N):
        for y in range(3):
            for x in range(3):
                if x == bx and y == by:
                    T[y][x] = 0
                    continue
                r = 0
                for dx, dy in dd:
                    nx = x + dx; ny = y + dy
                    if not 0 <= nx < 3 or not 0 <= ny < 3 or (bx == nx and by == ny):
                        nx = x; ny = y
                    r += S[ny][nx]
                T[y][x] = r
        S, T = T, S
    su = sum(sum(e) for e in S)
    print("%.15f" % (S[ty][tx] / su))

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

while True:
    n = input()
    if n == 0:
        break
    s, t, b = raw_input().split()
    s = ord(s) - ord('A')
    t = ord(t) - ord('A')
    b = ord(b) - ord('A')
    lst = [0.0 for i in range(9)]
    lst[s] = 1.0
    for loop in range(n):
        lst2 = [0.0 for i in range(9)]
        for i in range(9):
            x = i % 3
            y = i / 3
            if y > 0 and (y - 1) * 3 + x != b:
                lst2[(y - 1) * 3 + x] += lst[y * 3 + x] / 4
            else:
                lst2[y * 3 + x] += lst[y * 3 + x] / 4
            if y < 2 and (y + 1) * 3 + x != b:
                lst2[(y + 1) * 3 + x] += lst[y * 3 + x] / 4
            else:
                lst2[y * 3 + x] += lst[y * 3 + x] / 4
            if x > 0 and y * 3 + x - 1 != b:
                lst2[y * 3 + x - 1] += lst[y * 3 + x] / 4
            else:
                lst2[y * 3 + x] += lst[y * 3 + x] / 4
            if x < 2 and y * 3 + x + 1 != b:
                lst2[y * 3 + x + 1] += lst[y * 3 + x] / 4
            else:
                lst2[y * 3 + x] += lst[y * 3 + x] / 4
        lst = lst2
    print "%.10f" % lst[t]

Solution (Python):
while True:
  n = int(input())
  if n == 0:
    break

  s, t, b = input().split()
  base = ord("A")
  blank = ord(b) - base

  dp = [[0] * 9 for _ in range(n + 1)]
  dp[0][ord(s) - base] = 1

  to = {0:(0, 0, 1, 3), 1:(0, 1, 2, 4), 2:(1, 2, 2, 5), 3:(0, 3, 4, 6), 
        4:(1, 3, 5, 7), 5:(2, 4, 5, 8), 6:(3, 6, 6, 7), 7:(4, 6, 7, 8), 8:(5, 7, 8, 8)}
  
  def update(x, i):
    for nex in to[x]:
      if nex == blank:
        dp[i][x] += dp[i - 1][x] / 4
      else:
        dp[i][nex] += dp[i - 1][x] / 4

  for i in range(1, n + 1):
    for x in range(9):
      update(x, i)
  print(dp[n][ord(t) - base])