程序设计实习实验班2017作业(python 作业11)

2017年3月31日5,0770

1:热血格斗场

暴力可过。。。

import bisect

inf = 1000000000
    
set = []
bisect.insort(set, [inf, 1])
bisect.insort(set, [-inf, -1])
n = int(input())
for i in range(n):
    id, x = map(int, input().split())
    p = [x, id]
    r = bisect.bisect(set, p)
    l = r - 1
    if(x - set[l][0] <= set[r][0] - x):
        print(id, set[l][1])
    else:
        print(id, set[r][1])
    bisect.insort(set, p)

import bisect

inf = 1000000000

set = []

bisect.insort(set, [inf, 1])

bisect.insort(set, [-inf, -1])

n = int(input())

for i in range(n):

id, x = map(int, input().split())

p = [x, id]

r = bisect.bisect(set, p)

l = r - 1

if(x - set[l][0] <= set[r][0] - x):

print(id, set[l][1])

else:

print(id, set[r][1])

bisect.insort(set, p)

2:拯救行动

bfs

a = [''] * 200
xx = [0, 0, 1, -1]
yy = [-1, 1, 0, 0]
qx = [0] * 80000
qy = [0] * 80000
g = [0] * 80000
dis = [0] * 80000
mp = []

def bfs(bx, by):
    head = 0
    tail = 1
    qx[0] = bx
    qy[0] = by
    while head != tail:            
        x, y, st, d = qx[head], qy[head], g[head], dis[head]
        head = head + 1
        if st == 1:
            qx[tail] = x
            qy[tail] = y
            dis[tail] = d + 1
            g[tail] = 0
            tail = tail + 1
            continue
        for i in range(4):
            tx = x + xx[i]
            ty = y + yy[i]
            if tx < 0 or ty < 0 or tx >= n or ty >= m or a[tx][ty] == '#':
                continue
            if mp[tx][ty] == 0:
                if a[tx][ty] == 'a':
                    return d + 1
                mp[tx][ty] = 1
                qx[tail] = tx
                qy[tail] = ty
                g[tail] = (a[tx][ty] == 'x')
                dis[tail] = d + 1
                tail = tail + 1
    return -1

t = int(input())
for test in range(t):
    mp.clear()
    n, m = map(int, input().split())
    for i in range(n):
        mp.append([0] * 200)
        a[i] = input()
        for j in range(m):
            if(a[i][j] == 'r'):
                bx, by = i, j
    ans = bfs(bx, by)
    if ans == -1:
        print('Impossible')
    else:
        print(ans)

a = [''] * 200

xx = [0, 0, 1, -1]

yy = [-1, 1, 0, 0]

qx = [0] * 80000

qy = [0] * 80000

g = [0] * 80000

dis = [0] * 80000

mp = []

def bfs(bx, by):

head = 0

tail = 1

qx[0] = bx

qy[0] = by

while head != tail:

x, y, st, d = qx[head], qy[head], g[head], dis[head]

head = head + 1

if st == 1:

qx[tail] = x

qy[tail] = y

dis[tail] = d + 1

g[tail] = 0

tail = tail + 1

continue

for i in range(4):

tx = x + xx[i]

ty = y + yy[i]

if tx < 0 or ty < 0 or tx >= n or ty >= m or a[tx][ty] == '#':

continue

if mp[tx][ty] == 0:

if a[tx][ty] == 'a':

return d + 1

mp[tx][ty] = 1

qx[tail] = tx

qy[tail] = ty

g[tail] = (a[tx][ty] == 'x')

dis[tail] = d + 1

tail = tail + 1

return -1

t = int(input())

for test in range(t):

mp.clear()

n, m = map(int, input().split())

for i in range(n):

mp.append([0] * 200)

a[i] = input()

for j in range(m):

if(a[i][j] == 'r'):

bx, by = i, j

ans = bfs(bx, by)

if ans == -1:

print('Impossible')

else:

print(ans)

3:拨钟问题

python递归传参简直是玄学

f = [[0,1,3,4],[0,1,2],[1,2,4,5],[0,3,6],[1,3,4,5,7],[2,5,8],[3,4,6,7],[6,7,8],[4,5,7,8]]
mn = 100
ans = [0] * 40
st = []

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
now = a + b + c

def dfs(step):
    global mn, now, ans, st
    if(len(st) >= mn):
        return;
    if(now.count(0) == 9):
        mn = len(st)
        ans = st[:]
        return
    if(step == 9):
        return;
    for i in range(4):
        dfs(step + 1)
        for j in f[step]:
            now[j] = (now[j] + 1) % 4
        st.append(step)
    for i in range(4):
        st.pop()

dfs(0)
for i in ans:
    print(i + 1, end = ' ')

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

mn = 100

ans = [0] * 40

st = []

a = list(map(int, input().split()))

b = list(map(int, input().split()))

c = list(map(int, input().split()))

now = a + b + c

def dfs(step):

global mn, now, ans, st

if(len(st) >= mn):

return;

if(now.count(0) == 9):

mn = len(st)

ans = st[:]

return

if(step == 9):

return;

for i in range(4):

dfs(step + 1)

for j in f[step]:

now[j] = (now[j] + 1) % 4

st.append(step)

for i in range(4):

st.pop()

dfs(0)

for i in ans:

print(i + 1, end = ' ')

« 再见，OI 关于 OI 的一次问答记录 »

hzwer.com _ Home | http://hzwer.com

程序设计实习实验班2017作业(python 作业11)

1:热血格斗场

2:拯救行动

3:拨钟问题

分类目录

热门文章

Myfriends

近期评论