头像

Susu




离线:4天前


活动打卡代码 AcWing 845. 八数码

Susu
5天前
from collections import deque


def bfs(start):
    end = "12345678x"
    d = {start : 0} # 该字典存放每个状态距离初始状态的距离
    q = deque() # 存放将要验证的状态
    q.append(start)
    dx = [0, 1, 0, -1] # 用于"x"上下左右移动
    dy = [1, 0, -1, 0]
    while q:
        t = q.popleft()
        distance = d[t]
        if t == end:
            return distance
        k = t.index('x')
        x = k // 3 # 字符串的索引转换成3x3矩阵后的坐标
        y = k % 3

        tl = list(t) # 由于字符串不是不可变量,因而把字符串变为数组,用于交换字符串中的字符位置
        for i in range(4): # "x"上下左右移动
            a = x + dx[i]
            b = y + dy[i]
            if a >=0 and a < 3 and b >=0 and b < 3: # 若坐标未超出矩阵范围
                nk = a * 3 + b #3x3矩阵的坐标转换成字符串的索引
                tl[nk], tl[k] = tl[k], tl[nk] # 交换字符串中的字符位置
                t = "".join(tl)
                if t not in d: # 如果t这个状态是新状态(之前未出现过)
                    q.append(t)
                    d[t] = distance + 1
                tl[nk], tl[k] = tl[k], tl[nk] # 还原现场
    return -1



start = input().replace(" ", "")
ans = bfs(start)
print(ans)

作者:机械佬也想学编程
链接:https://www.acwing.com/solution/content/15909/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 844. 走迷宫

Susu
5天前

def bfs():
d[0][0] = 0
queue = [(0, 0)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

while queue : #队列不为空
    x, y = queue.pop(0)
    for i in range(4):
        a = x + dx[i];
        b = y + dy[i];
        if a >= 0 and a < n and b >= 0 and b < m and g[a][b] == 0 and d[a][b] == -1:
            queue.append((a,b))#入队
            d[a][b] = d[x][y] + 1
print(d[n - 1][m - 1])

main

n, m = map(int, input().split())#map函数对分割输入后的字符列表转换成整型
g = [[-1 for j in range(m)] for i in range(n)] # 存储地图

for i in range(n):
in_li = list(map(int, input().split()))
for j in range(m):
g[i][j] = in_li[j];
d = [[-1 for i in range(m)] for j in range(n)]#初始化为 - 1
bfs()



新鲜事 原文

Susu
4个月前
1024打折开心


活动打卡代码 AcWing 843. n-皇后问题

Susu
4个月前
N = 24
n = int(input())
path = [0]*N
g = []
for i in range(n):
    g.append('.'*n)
col, dg, udg = [0]*N, [0]*N, [0]*N

def dfs(u):
    if u == n: 
        for j in range(n): 
            print(g[j])
        print(" ")

    for i in range(n):
        if (col[i] == 0 and dg[u + i] == 0 and udg[n - u + i] == 0):
            if i == 0:
                g[u] = 'Q' + g[u][i+1:]
            elif i == -1:
                g[u] = g[u][:i] + 'Q'
            else:
                g[u] = g[u][:i] + 'Q' + g[u][i+1:]
            col[i] = dg[u + i] = udg[n - u + i] = 1
            dfs(u + 1)
            col[i] = dg[u + i] = udg[n - u + i] = 0
            if i == 0:
                g[u] = '.' + g[u][i+1:]
            elif i == -1:
                g[u] = g[u][:i] + '.'
            else:
                g[u] = g[u][:i] + '.' + g[u][i+1:]

dfs(0)


活动打卡代码 AcWing 842. 排列数字

Susu
4个月前
N = 10
n = int(input())
path = [0]*N
st = [0]*N

def dfs(u):
    if u == n:
        for i in range(n):
            if i == n - 1:
                print(path[i])
            else:
                print(path[i],end = " ")

    for i in range(1,n + 1):
        if st[i] != 1:
            path[u] = i
            st[i] = 1
            dfs(u + 1)
            st[i] = 0

dfs(0)


活动打卡代码 AcWing 240. 食物链

Susu
4个月前
N = 50010

n,k = map(int,input().split())
p,d = [0]*N, [0]*N
def find(x):
    if x != p[x]:
        t = find(p[x])
        d[x] += d[p[x]]
        p[x] = t
    return p[x]

for i in range(1,n+1):
    p[i] = i

res = 0
for i in range(k):
    t,x,y = map(int,input().split())
    if x > n or y > n: res += 1
    else:
        px,py = find(x), find(y)
        if t == 1:
            if px == py and (d[x] - d[y]) % 3: res += 1
            elif px != py:
                p[px] = py
                d[px] = d[y] - d[x]
        else:
            if px == py and (d[x] - d[y] - 1) % 3: res += 1
            elif px != py:
                p[px] = py
                d[px] = d[y] + 1 - d[x]
print(res)


活动打卡代码 AcWing 841. 字符串哈希

Susu
4个月前
N, P = 100010, 131
mod = 998244353
n, m = map(int,input().split())
string = str(input()) + " " * (N - n)
h, p = [0] * N, [1] * N
# p[0] = 1

def get(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % mod

for i in range(1,n+1):
    p[i] = (p[i - 1] * P) % mod
    h[i] = (h[i - 1] * P + ord(string[i - 1])) % mod

for j in range(m):
    l1, r1, l2, r2 = map(int, input().split())
    if get(l1, r1) == get(l2, r2): print("Yes")
    else: print("No")


活动打卡代码 AcWing 840. 模拟散列表

Susu
4个月前

拉链法

N = 100003
n = int(input())
h, e, ne = [-1]*N, [0]*N, [0]*N
idx = 0

def insert(x):
    global idx
    k = x % N
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx += 1

def find(x):
    k = x % N
    i = h[k]
    while i != -1:
        if e[i] == x:
            return True
        i = ne[i]
    return False

for i in range(n):
    s, p = map(str,input().split())
    p = int(p)
    if s == "I": insert(p)
    else:
        if find(p): print("Yes")
        else: print("No")
    # print(h[0:5])    

开放寻址法

N = 200003
null = 0x3f3f3f3f
n = int(input())
h = [null]*N
idx = 0

def insert(x):
    global idx
    k = x % N
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx += 1

def find(x):
    k = x % N
    while h[k] != null and h[k] != x:
        k += 1
        if (k == N): k = 0
    return k

for i in range(n):
    s, p = map(str,input().split())
    p = int(p)
    k = find(p)
    if s == "I":
        h[k] = p
    else:
        k = find(p)
        if h[k] != null: print("Yes")
        else: print("No")
    # print(h[0:5])    


活动打卡代码 AcWing 839. 模拟堆

Susu
4个月前
N = 100010

n = int(input())
m = 0
h, ph, hp = [0]*N, [0]*N, [0]*N
size = 0

# 堆互换
def heap_swap(a,b):
    ph[hp[a]], ph[hp[b]] = ph[hp[b]], ph[hp[a]]
    hp[a], hp[b] = hp[b], hp[a]
    h[a],h[b] = h[b],h[a]

def down(u):
    t = u
    if (u * 2 <= size and h[u * 2] < h[t]): t = 2 * u
    if (u * 2 + 1 <= size and h[u * 2 + 1] < h[t]): t = u * 2 + 1
    if (u != t):
        heap_swap(t,u)
        # 普通互换
        # h[u], h[t] = h[t], h[u]
        down(t)

def up(u):
    while u // 2 and h[u // 2] > h[u]:
        heap_swap(u // 2, u)
        # h[u // 2], h[u] = h[u], h[u // 2]
        u = u // 2

for i in range(n):
    s, *p = input().split()
    p = list(map(int,p))
    if s == "I":
        size += 1
        m += 1
        ph[m] = size
        hp[size] = m
        h[size] = p[0]
        up(size)
    elif s == "PM": print(h[1])
    elif s == "DM":
        heap_swap(1,size)
        size -= 1
        down(1)
    elif s == "D":
        p[0] = ph[p[0]]
        heap_swap(p[0], size)
        size -= 1
        down(p[0])
        up(p[0])
    else:
        p[0] = ph[p[0]]
        h[p[0]] = p[1]
        down(p[0])
        up(p[0])



活动打卡代码 AcWing 838. 堆排序

Susu
4个月前
N = 100010

n,m = map(int,input().split())
h = [0]*N

def down(u):
    t = u
    if (u * 2 <= size and h[u * 2] < h[t]): t = 2 * u
    if (u * 2 + 1 <= size and h[u * 2 + 1] < h[t]): t = u * 2 + 1
    if (u != t):
        h[u], h[t] = h[t], h[u]
        down(t)

h[0:n] = list(map(int,input().split()))
for i in range(1,n+1):
    size = n
for i in range(n//2,-1,-1): down(i)
for i in range(m):
    print(h[1], end = " ")
    h[1] = h[size]
    size -= 1
    down(1)