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



Sample input:
1
E A C
1
E B C
2
E A B
0


Sample output:
0.00000000
0.25000000
0.06250000

Submission status: Wrong Answer

Solution code:
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()
	print count_d,"reset"
	
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
	print count_d,"preset"
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]
		print count_d,"repeat",i
		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)),count_d[info[1]],float((4**time))

Submission status: Wrong Answer

Solution code:
def cnv(c):
    rm='ABCDEFGHI'
    id=[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
    return id[rm.index(c)]
 
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        [s,t,b]=[cnv(c) for c in raw_input().split()]
        A=[[0 for i in range(5)] for j in range(5)]
        B=[[0 for i in range(5)] for j in range(5)]
        A[s[0]][s[1]]=1
        for i in range(n):
            for j in range(1,4):
                for k in range(1,4):
                    B[j][k]=(A[j+1][k]+A[j-1][k]+A[j][k+1]+A[j][k-1])*0.25
            B[b[0]][b[1]]=0 
            for j in range(1,4):
                A[j][1:4]=B[j][1:4]
        print A[t[0]][t[1]]

Submission status: Wrong Answer

Solution code:
pos={"A":(0,0),"B":(1,0),"C":(2,0),"D":(0,1),"E":(1,1),"F":(2,1),
     "G":(0,2),"H":(1,2),"I":(2,2)}
mv=((0,1),(0,-1),(1,0),(-1,0))

def dfs(x,y,n):
    global prob
    if n==0:
        return 1.0 if (x,y)==t else 0.0
    if (x,y,n) in dp:
        return dp[(x,y,n)]
    for dx,dy in mv:
        mx=x+dx
        my=y+dy
        if mx<0 or mx>2 or my<0 or my>2 or (mx,my)==b:
            prob+=0.25*dfs(x,y,n-1)
        else:
            prob+=0.25*dfs(mx,my,n-1)
        dp[(x,y,n)]=prob
    return prob

while True:
    n=input()
    if n==0:break
    s,t,b=raw_input().split()
    s,t,b=pos[s],pos[t],pos[b]
    dp={}
    prob=0.0
    print dfs(s[0],s[1],n)

Submission status: Wrong Answer

Solution code:
pos={"A":(0,0),"B":(1,0),"C":(2,0),"D":(0,1),"E":(1,1),"F":(2,1),
     "G":(0,2),"H":(1,2),"I":(2,2)}
mv=((0,1),(0,-1),(1,0),(-1,0))

def dfs(x,y,n):
    global prob
    if n==0:
        return 1.0 if (x,y)==t else 0.0
    if (x,y,n) in dp:
        return dp[(x,y,n)]
    for dx,dy in mv:
        mx=x+dx
        my=y+dy
        if mx<0 or mx>2 or my<0 or my>2 or (mx,my)==b:
            prob+=0.25*dfs(x,y,n-1)
        else:
            prob+=0.25*dfs(mx,my,n-1)
        dp[(x,y,n)]=prob
    return prob

while True:
    n=input()
    if n==0:break
    s,t,b=raw_input().split()
    s,t,b=pos[s],pos[t],pos[b]
    dp={}
    prob=0.0
    print "%.8f"%dfs(s[0],s[1],n)

Submission status: Wrong Answer

Solution code:
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[:]
                for x in range(9):
                        Prob[x] = 0
                        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]]]))

Submission status: Wrong Answer

Solution code:
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[:]
                for x in range(9):
                        Prob[x] = 0
                        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(Prob[Room[Info[1]]])

Submission status: Wrong Answer

Solution code:
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

        for x in range(3):
                print(Prob[x*3:x*3+3])
        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
                for x in range(3):
                        print(Prob[x*3:x*3+3])

        print(Prob[Room[Info[1]]])

Submission status: Wrong Answer

Solution code:
dic = {"A":(0,0), "B":(0,1), "C":(0,2),
       "D":(1,1), "E":(1,1), "F":(1,2),
       "G":(2,1), "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(dp[n][dic[t][0]][dic[t][1]] / float(sum(reduce(lambda a, b: a + b, dp[n]))))

Submission status: Time Limit Exceeded

Solution code:
pos={"A":(0,0),"B":(1,0),"C":(2,0),"D":(0,1),"E":(1,1),"F":(2,1),
     "G":(0,2),"H":(1,2),"I":(2,2)}
mv=((0,1),(0,-1),(1,0),(-1,0))

def dfs(x,y,n):
    global prob
    if n==0:
        return 1.0 if (x,y)==t else 0.0
    for dx,dy in mv:
        mx=x+dx
        my=y+dy
        if mx<0 or mx>2 or my<0 or my>2 or (mx,my)==b:
            prob+=0.25*dfs(x,y,n-1)
        else:
            prob+=0.25*dfs(mx,my,n-1)
    return prob

while True:
    n=input()
    if n==0:break
    s,t,b=raw_input().split()
    s,t,b=pos[s],pos[t],pos[b]
    prob=0.0
    prob=dfs(s[0],s[1],n)
    print prob

Submission status: Time Limit Exceeded

Solution code:
mv = ((0, 1), (1, 0), (0, -1), (-1, 0))
conv = {'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)
        }


def rec(x, y, energy, prob):
    global ans
    if energy == 0:
        if (x, y) == conv[t]:
            ans += prob
        return

    for dx, dy in mv:
        mx = x + dx
        my = y + dy
        if mx < 0 or mx >= 3 or my < 0 or my >= 3 or (mx, my) == conv[b]:
            rec(x, y, energy-1, prob*0.25)
        else:
            rec(mx, my, energy-1, prob*0.25)


while True:
    n = input()
    if n == 0:
        break
    ans = 0
    s, t, b = raw_input().split()
    x, y = conv[s]
    rec(x, y, n, 1.0)
    print '%.8f' % ans

Submission status: Accepted

Solution code:
# AOJ 1020: Cleaning Robot
# Python3 2018.7.5 bal4u

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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]

Submission status: Accepted

Solution code:
#!/usr/bin/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):
                # up
                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)]

                # down
                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)]

                # left
                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)]

                # right
                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

Submission status: Accepted

Solution code:
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]]]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env 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]

Submission status: Accepted

Solution code:
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])