bfs个人总结

bfs本质上就是一种巧妙的暴力搜索，遵循有限规则遍历层次结构得到最优解。
可分为两种：

• 从一点到另一点
• 从一种状态到另一种状态

本题就是状态的遍历。

AC过程

明确条件：初始结束状态，有限规则，可以用。
准备工作：队列直接存储列表；状态用集合存储字符串（很容易想到二进制）；距离用字典（健用字符串）【其实主要就是一点——状态的存储表示方式】
编写：遍历每个状态下每个点可以做的每个操作
踩坑：

1. 还不熟悉Python环境
   Python按对象引用传递而C++按值传递，所以Python传入函数参数后直接会更改，需要复制。
   Set集合创建时加入可迭代对象要加上[]，不然如字符串就会被拆开。
2. 超时
   最开始复制原参是用的deepcopy（递归实现，慢的很），只能过5个；后来改成手动复制，有时过9个，有时过10个能AC；再把字符串拼接换成元组，算是正式AC了。

Python3 代码

from collections import deque

def change(g):
    return tuple(tuple(row) for row in g)
    '''
    bn=str()
    for i in range(4):
        tmp=''.join(map(str,g[i]))
        bn+=tmp
    return bn
    '''

def swap(t,i,j,k):   #默认传参更改原值
    #deepcopy
    g=[row[:] for row in t]   
    g[i][j],g[i+dx[k]][j+dy[k]]=g[i+dx[k]][j+dy[k]],g[i][j]
    return g

def bfs():
    ans=0
    q=deque()
    q.append(begin)
    st=set([change(begin)])   #set传入可迭代元素需用[]框出
    dis={change(begin):0}
    while q:
        t=q.popleft()
        t_str=change(t)
        if t==end:
            return dis[t_str]
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    if 0<=i+dx[k]<=3 and 0<=j+dy[k]<=3:
                        nt=swap(t,i,j,k)
                        nt_str=change(nt)
                        if nt_str in st:
                            continue
                        dis[nt_str]=dis[t_str]+1
                        st.add(nt_str)
                        q.append(nt)

dx=[0,0,1,-1]
dy=[1,-1,0,0]
begin=[]
end=[]
for _ in range(4):
    begin.append(list(map(int,input())))
input()
for _ in range(4):
    end.append(list(map(int,input())))
print(bfs())