28170: 算鹰

dfs, http://cs101.openjudge.cn/practice/28170/

注意看，这个男人叫小帅。他今天在云顶之弈中有所感悟，决定和捷豹在围棋领域扳扳手腕。他注意到，对于自己的棋子(如下O)，其上下左右四个位置（如下'!'所示）极其关键。如果四个位置都被对方棋子占领（如下）那么自己的棋子就会因为没有“气”而被提子。

#!#

!O!

#!#

而如果这四个位置有己方的子，则可以连成整体，整体的“气”更多，更难被提子。小帅决定称自己通过上下左右四个方向连成一起的整体为“鹰”，以表示其蓬勃的生机。现在他有一个10x10的小棋盘，其中'-'表示空位，'.'表示自己的落子，他想写一个程序，看看自己有多少“鹰”。

输入

输入为 10x10的字符，表示棋盘局势，'-'表示空位，'.'表示己方落子

输出

输出为一个int数，表示己方“鹰”的数量。

样例输入

---.--.-..
-..-.-....
...--....-
----......
--.---....
-.-..-.---
....-.-..-
-..-----..
-.......-.
.....--.--

样例输出

提示

可以利用深度优先遍历进行求解。

这个题目描述不清楚。不如 02386:Lake Counting 题目好。http://cs101.openjudge.cn/practice/02386/

python

def dfs(x,y):
    graph[x][y] = "-"
    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        if 0<=x+dx<10 and 0<=y+dy<10 and graph[x+dx][y+dy] == ".":
            dfs(x+dx,y+dy)
graph = []
result = 0
for i in range(10):
    graph.append(list(input()))
for i in range(10):
    for j in range(10):
        if graph[i][j] == ".":
            result += 1
            dfs(i,j)
print(result)

28170: 算鹰 ​

28170: 算鹰