第十三届蓝桥杯模拟赛 1 期 平面图连通

本文主要是介绍第十三届蓝桥杯模拟赛 1 期 平面图连通，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题描述
　　著名设计师小蓝给蓝桥小学设计了一个教学楼。
　　蓝桥小学经常下雨，所以校长希望教学楼任何地方都可以连通到其它地方。
　　小蓝给出了教学楼的平面图，用一个 n 行 m 列的 01 矩阵表示，其中 0 表示空地，1 表示教学楼。两个相邻的 1 （上下相邻或左右相邻）之间互相可达。
　　请帮小蓝检查一下，是否教学楼的任意两个地方都可以连通到其它地方。
输入格式
　　输入的第一行包含两个整数 n, m，用一个空格分隔。
　　接下来 n 行，每行一个长度为 m 的 01 串，表示教学楼的平面图。
输出格式
　　如果满足要求，输出“YES”，否则输出“NO”，请注意字母全部都是大写。

n, m = map(int, input().split())  # 读入输入的行列，和n行每行一个长度为 m 的 01 串
hang = []
All = []
for i in range(n):
    hang = list(map(int, input()))
    All.append(hang)

visit = [[0 for i in range(m)] for j in range(n)]  # visit矩阵来记录走过的位置


def DFS(x, y):
    visit[x][y] = 1  # 表示此点已经搜索过
    fangxiang = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
    for dx, dy in fangxiang:
        if dx < 0 or dx > n - 1 or dy < 0 or dy > m - 1:
            continue  # 如果是边框，跳过此方向
        elif visit[dx][dy] == 0:
            if All[dx][dy] == 0:
                continue
            elif All[dx][dy] == 1:
                DFS(dx, dy)
        elif visit[dx][dy] == 1:
            continue
    return


def find():
    for i in range(n):
        for j in range(m):
            if All[i][j] == 1:
                DFS(i, j)
                return


find()

if All == visit:
    print("YES")
else:
    print("NO")

在网上找了个遍都没找到python版本的，没办法，自己写吧

思路参考：深度优先搜索及python实现围棋“吃子”_吃草的哥哥哥斯拉的博客-CSDN博客_python围棋算法

这篇关于第十三届蓝桥杯模拟赛 1 期 平面图连通的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！