Solve Lake Counting (POJ NO.2386) with Python3

Ant book exercises beginner's edition

I am studying for a competition professional. I have solved Lake Counting, which is famous for search problems, using Python, so I will post it. Many people solve it with a recursive function, but I solved it with a stack (recursive is not possible yet ...) Below is the implemented code. I've only tried two test cases, so I'm sorry if there are any patterns that I can't handle.

lakecounting.py


n,m=map(int,input().split())
field=[list(input()) for i in range(n)]
visited = [[0 for i in range(m)] for j in range(n)]
move = [[0,1],[1,0],[1,1],[0,-1],[-1,0],[-1,-1],[1,-1],[-1,1]]

cnt=0

for i in range(n):
    for j in range(m):
        if field[i][j] == "W" and visited[i][j]==0:
            sx,sy=i,j
            stack=[[sx,sy]]
            visited[sx][sy]=1
            while stack:
                x,y = stack.pop()
                for k in range(8):
                    nx,ny = x+move[k][0],y+move[k][1]
                    if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0 and field[nx][ny]=="W":
                        stack.append([nx,ny])
                        visited[nx][ny]=1
            cnt += 1
print(cnt)

It is written in the form of receiving standard input. Please point out any mistakes.

Recommended Posts

Solve Lake Counting (POJ NO.2386) with Python3
Solve POJ 2386 with python
Solve AtCoder 167 with python
Solve Sudoku with Python
[Python] Solve equations with sympy
Solve AtCoder ABC166 with python
Solve AtCoder ABC 186 with Python
solver> Link> Solve Excel Solver with python
Solve ABC163 A ~ C with Python
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solve ABC168 A ~ C with Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
Suddenly with Python PyInstaller No module named pyinstaller
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
I wanted to solve ABC172 with Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
FizzBuzz with Python3
Scraping with Python
Statistics with python
Let's solve simultaneous linear equations with Python sympy!
I wanted to solve NOMURA Contest 2020 with Python
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Play with 2016-Python
Solve A ~ D of yuki coder 247 with python
AES256 with python
Tested with Python
python starts with ()
with syntax (Python)
I want to solve APG4b with Python (Chapter 2)
Zundokokiyoshi with python
Parallel processing with no deep meaning in Python
Easy Lasso regression analysis with Python (no theory)
Solve "AtCoder version! Ant book (beginner)" with Python!
Excel with Python
Microcomputer with Python
Cast with python
Try to solve the programming challenge book with python3
Try to solve the internship assignment problem with Python
I tried to solve the soma cube with python
Solve simultaneous ordinary differential equations with Python and SymPy.
Solve higher-order equations with integer type (no multiple solutions)
I tried to solve the problem with Python Vol.1
I tried to solve AOJ's number theory with Python
Serial communication with Python
Zip, unzip with python
Django 1.11 started with Python3.6
Primality test with Python
Python with eclipse + PyDev.
Socket communication with Python
Data analysis with python 2
Scraping with Python (preparation)
Solve ABC168D in Python
Learning Python with ChemTHEATER 03
Sequential search with Python
Solve ABC167-D in Python