[a982. 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982)

def bfs():
    queue = [(1, 1, 1)] 
    bol[1][1] = 0 
    while queue:
        x, y, steps = queue.pop(0)
        if x == n - 2 and y == n - 2:
            return steps
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and z[nx][ny] == "." and bol[nx][ny] == 1:
                bol[nx][ny] = 0
                queue.append((nx, ny, steps + 1))
    return "No solution!"
n = int(input())
z = [list(input().strip()) for _ in range(n)]
bol = [[1 if z[i][j] == "." else 0 for j in range(n)] for i in range(n)]
dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
print(bfs())

計算路徑延伸需回朔

def bfs():
    queue = [(1, 1, 1)] 
    bol[1][1] = 0
    parents = {}
    while queue:
        x, y, steps = queue.pop(0)
        if x == n - 2 and y == n - 2:
            results = [(x,y)]
            cur = parents[(x,y)]
            while cur:
                results.append(cur)
                cur = parents.get(cur)
            results.reverse()
            return steps,results
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and z[nx][ny] == "." and bol[nx][ny] == 1:
                bol[nx][ny] = 0
                parents[(nx,ny)] = (x,y)
                queue.append((nx, ny, steps + 1))
    return "No solution!"
n = int(input())
z = [list(input().strip()) for _ in range(n)]
bol = [[1 if z[i][j] == "." else 0 for j in range(n)] for i in range(n)]
dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
a,b = bfs()
print(a)
for i in b:
    print(i)

[a597. 祖靈被榨乾了!!!!!!!!](https://zerojudge.tw/ShowProblem?problemid=a597)

n, m = map(int,input().split())
z = []
for i in range(n):
    z.append(list(input()))
bol = [[1 if z[i][j] == "J" else 0 for j in range(m)] for i in range(n)]
def bfs(x,y):
    dx = [0, 1, -1, 0]
    dy = [1, 0, 0, -1]
    queue = [(x, y)] 
    area = 1
    bol[x][y] = 0
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m  and bol[nx][ny] == 1:
                bol[nx][ny] = 0
                queue.append((nx, ny))
                area += 1
    return area
ma = 0;ans = 0
for i in range(n):
    for j in range(m):
        if z[i][j] == "J" and bol[i][j] == 1:
            ma = max(ma,bfs(i,j))
            ans += 1
print(ans,ma)

[#T1212. LETTERS](https://oj.qiaosicode.com/p/T1212)

n, m = map(int,input().split())
z = []
for i in range(n):
    z.append(list(input()))
def bfs(x,y):
    dx = [0, 1, -1, 0]
    dy = [1, 0, 0, -1]
    queue = [(x, y)]
    se = [z[x][y]]
    area = 1
    while queue:
        print(se)
        x, y = queue.pop(0)
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m  and z[nx][ny] not in se:
                se.append(z[nx][ny])
                queue.append((nx, ny))
                area += 1
    return area
print(bfs(0,0))

[#T1199. 全排列](https://blog.csdn.net/fight_andy/article/details/136141005)

z = []
def dfs(ls,start,end):
    global z
    if start >= end:
        z.append(ls.copy())
    else:
        for i in range(start,end+1):
            ls[start] ,ls[i] = ls[i],ls[start]
            dfs(ls,start+1,end)
            ls[start] ,ls[i] = ls[i],ls[start]
n = input()
dfs(list(n),0,len(n)-1)
for i in z:
    print(*i)

[#T1215. 迷宫](https://blog.csdn.net/lan_in/article/details/136993666?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-1-136993666-blog-126461074.235%5Ev43%5Epc_blog_bottom_relevance_base2&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-1-136993666-blog-126461074.235%5Ev43%5Epc_blog_bottom_relevance_base2&utm_relevant_index=1)

n = int(input())
z = []
for i in range(n):
    z.append(list(input()))
bol = [[1 for j in range(n)] for i in range(n)]
dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
for i in range(n):
    for j in range(n):
        if z[i][j] == ".":
            bol[i][j] = "0"
a, b, c, d = map(int,input().split())
def dfs(x,y,c,d):
    queue = [[x,y]]
    bol[x][y] = 1
    while queue:
        x,y = queue.pop(0)
        if x == c and y == d:
            return "YES"
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and z[nx][ny] == "." and bol[nx][ny] == "0":
                queue.append([nx,ny])
                bol[nx][ny] = 1
    return "NO"
print(dfs(a,b,c,d))

八皇后問題

ans = [0] * 10
su = 0
def out():
    z = []
    for i in range(1,9):
        z.append(ans[i])
    print(z)
def is_safe(n, k):
    for i in range(1, n):
        #不能在同一直線        #水平距離 之前的水平列減去當前的水平列
        if ans[i] == k or abs(ans[i] - k) == abs(n - i):
            return False                 #垂直距離 當前行減之前垂直行的點
    return True
def dfs(n):
    if n == 9:  # 當 n 等於 9 時，表示已經放置了 8 個皇后
        out()
        return
    for i in range(1, 9):
        if is_safe(n, i):  # 第n行第i列放上旗子
            ans[n] = i
            dfs(n + 1)
            ans[n] = 0
dfs(1)

輸出有幾塊不同的區域
5 5
AABBB
AABBB
CCCCC
CCBBB
BBBBB

dx = [1,-1,0,0]
dy = [0,0,1,-1]
def dfs(x,y,k):
    bol[x][y] = 0
    queue = [[x,y]]
    ans = 1
    while queue:
        xx,yy = queue.pop(0)
        for i in range(4):
            nx = xx + dx[i]
            ny = yy + dy[i]
            if 0 <= nx < n and 0 <= ny < m and z[nx][ny] == k and bol[nx][ny] == 1:
                bol[nx][ny] = 0
                ans += 1
                queue.append([nx,ny])
    return 1
n,m = map(int,input().split())
z = []
bol = [[1 for i in range(m)]for i in range(n)]
for i in range(n):
    z.append(list(input()))
ans = 0;
for i in range(n):
    for j in range(m):
        if bol[i][j] == 1:
            dfs(i,j,z[i][j])
            ans += 1
print(ans)