我的C++的双向bfs能AC，但python的双向bfs会有几个测试点tle

我用python版的普通bfs是能够AC的，应该不是python跑的慢的问题

先贴一下AC的C++版本

#include<iostream>
#include<cstdio>
#include<iostream>
#include<map>
#include<queue>
#include<string>
using namespace std;

// 右下左上
const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };

int bfs(string x, string y)
{
	queue<string> head, tail;  // 两个队列
	map<string, int> d_head, d_tail;
	head.push(x);
	d_head[x] = 0;
	tail.push(y);
	d_tail[y] = 0;
	while (head.size() && tail.size()){
		if (head.size() <= tail.size()){
			string temp = head.front();
			head.pop();

			int k = temp.find('0');
			int x = k / 3, y = k % 3;
			for (int i = 0; i < 4; i++){
				int tx = x + dx[i];
				int ty = y + dy[i];
				if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3){
					string str = temp;
					swap(str[k], str[3 * tx + ty]);
					if (d_tail.count(str)) // 相遇，则可以返回
						return d_head[temp] + 1 + d_tail[str];
					if (!d_head.count(str)){
						head.push(str);
						d_head[str] = d_head[temp] + 1;
					}
				}
			}
		}
		else{ // 原理相同，就是把head的地方改成tail，把tail的地方改成head即可
			string temp = tail.front();
			tail.pop();

			int k = temp.find('0');
			int x = k / 3, y = k % 3;
			for (int i = 0; i < 4; i++){
				int tx = x + dx[i];
				int ty = y + dy[i];
				if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3){
					string str = temp;
					swap(str[k], str[3 * tx + ty]);
					if (d_head.count(str))
						return d_tail[temp] + 1 + d_head[str];
					if (!d_tail.count(str)){
						tail.push(str);
						d_tail[str] = d_tail[temp] + 1;
					}
				}
			}
		}
	}
	return -1; // 无解
}
int main(){
	string start, end, seq;
	end = "123804765";
	getline(cin, start);
	if (start == end) // 如果相等就可以直接输出了
		printf("0");
	else printf("%d", bfs(start, end));
	return 0;
}

python版是依照C++版本来写的，有没有大佬帮忙看看哪里写错了

from collections import deque
# 右下左上
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def bfs(start, end):
    q_head = deque()
    q_tail = deque()
    q_head.append(start)
    q_tail.append(end)
    d_head = {start: 0}
    d_tail = {end: 0}

    while q_head and q_tail:
        if q_head.__len__() <= q_tail.__len__():
            temp = q_head.popleft()
            k = temp.index('0')
            x = k // 3
            y = k % 3
            tl = list(temp)
            for i in range(4):
                tx = x + dx[i]
                ty = y + dy[i]
                if 0 <= tx < 3 and 0 <= ty < 3:
                    tl[k], tl[3 * tx + ty] = tl[3 * tx + ty], tl[k]
                    str = "".join(tl)
                    if str in d_tail:
                        return d_head[temp] + 1 + d_tail[str]
                    else:
                        q_head.append(str)
                        d_head[str] = d_head[temp] + 1
                    tl[k], tl[3 * tx + ty] = tl[3 * tx + ty], tl[k]

        else:
            temp = q_tail.popleft()
            k = temp.index('0')
            x = k // 3
            y = k % 3
            tl = list(temp)
            for i in range(4):
                tx = x + dx[i]
                ty = y + dy[i]
                if 0 <= tx < 3 and 0 <= ty < 3:
                    tl[k], tl[3 * tx + ty] = tl[3 * tx + ty], tl[k]
                    str = "".join(tl)
                    if str in d_head:
                        return d_tail[temp] + 1 + d_head[str]
                    else:
                        q_tail.append(str)
                        d_tail[str] = d_tail[temp] + 1
                    tl[k], tl[3 * tx + ty] = tl[3 * tx + ty], tl[k]
    return -1


start = input()
end = "123804765"
if start == end:
    print("0")
else:
    print(bfs(start, end))