[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]

** Aim for a light blue coder! !! !! !! !! !! ** **

So [Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)

AtCoder has collected 100 good educational questions that are appropriate for brown and green coders to achieve a light blue coder, or rating 1200, with a small number of questions.

100 past questions that beginners and intermediates should solve in this article` Will be solved with ** Python **! Thanks to @ e869120! !! !! !! !! !!

Past article link

** Search all: List all ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22] ** Full search: All enumeration to reduce the number of streets by devising ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] ** Full search: Bit full search ** [[Python] I tried to solve 100 selected past questions that beginners and intermediates should solve [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Full search: Permutation full search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part4 / 22] ** Binary search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part5 / 22] ** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22] ** Breadth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]

"Part 7" -Breadth-first search (BFS)-

We will solve the following 6 questions!

Breadth-first search

28 ALDS_11_C --Breadth-first search This is a basic problem. 29 AtCoder Beginner Contest 007 C --Breadth-first search The shortest path problem of a weightless graph can be solved by breadth-first search. 30 JOI 2011 Qualifying 5-Cheese 31 JOI 2012 Qualifying 5-Illuminations The implementation is a little heavy, but if you do your best, you can solve it. 32 AOJ 1166 --Maze and order The implementation is a little heavy. 33 AtCoder Beginner Contest 088 D --Grid Repainting If this is solved, you can think that you are accustomed to breadth-first search.

BFS prerequisites

・ I will write an article based on the following two points! ** ① Understanding DFS to some extent ** The BFS implementation method is almost the same as the DFS implementation method! (Just use the queue instead of the stack!) First, let's understand DFS!

** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22]

② About BFS Kenchon's article BFS (Breadth-first Search) Super Introduction! ~ Use the queue vividly ~ Read about BFS ** Understand the atmosphere! ** **

(No weight) BFS is also useful for the shortest path problem of graphs! !! !!

If you have the premise of ①②, you can learn it by actually moving your hands! !! !!

28 ALDS_11_C --Breadth-first search

The implementation method of BFS is the same as DFS ** The housekeeper saw! Just put (seen) and "queue" ** is! (For those who don't understand what they are saying, see Past Articles!)

BFS was a stack, but DFS was queued, When dequeuing, it's popleft ()!

Let's create min_dist as a variable ~ ** It was unexpectedly easy to implement! !! !! ** **

test.py


import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
    u,k,*v = x
    for y in v:
        graph[u].append(y)
seen = [0]*(n+1) #1_indexed
min_dist = [-1]*(n+1) #1_indexed
queue = collections.deque() #Put the vertex NO
def bfs():
    seen[1] = 1
    queue.append(1)
    min_dist[1] = 0
    while queue:
        q_NO = queue.popleft()
        q_dist = min_dist[q_NO]
        if not graph[q_NO]:
            continue
        g = graph[q_NO]
        for _ in range(len(g)):
            g_NO = g.popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            queue.append(g_NO)
            min_dist[g_NO] = q_dist+1
bfs()
for i,ans in enumerate(min_dist[1:],1):
    print(i,ans)

29 AtCoder Beginner Contest 007 C Difficulty:1003 It's a typical shortest path problem! It's almost the same as DFS's grid bluff problem ~ I was able to implement this problem even **! ** **

test.py


import collections,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
R,C = LI()
sy,sx = [i-1 for i in LI()]
gy,gx = [i-1 for i in LI()]
c = [S() for _ in range(R)]
drdc = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*C for _ in range(R)]
seen = [[0]*C for _ in range(R)]
queue = collections.deque() #position[line,Column]Put in
def bfs():
    seen[sy][sx] = 1
    queue.append([sy,sx])
    min_dist[sy][sx] = 0
    while queue:
        qr,qc = queue.popleft()
        for dr,dc in drdc:
            nr,nc = qr+dr,qc+dc
            if c[nr][nc]=='#' or seen[nr][nc]:
                continue
            if [nr,nc]==[gy,gx]:
                return min_dist[qr][qc]+1
            seen[nr][nc] = 1
            queue.append([nr,nc])
            min_dist[nr][nc] = min_dist[qr][qc]+1
print(bfs())

30 JOI 2011 Qualifying 5-Cheese

Again, the problem is a little more complicated, but the idea is exactly the same as the previous problem ~ This problem was also solved ** without difficulty ~ **

test.py


import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W,N = LI()
area = [S() for _ in range(H)]
ans = 0
S_factory_point = [[-1,-1] for _ in range(N+1)] #1_indexed
for h,w in itertools.product(range(H),range(W)):
    if area[h][w]=='S':
        S_factory_point[0] = [h,w]
    if area[h][w] in list(map(str,list(range(1,N+1)))):
        S_factory_point[int(area[h][w])] = [h,w]
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
def bfs(sh,sw,target_factory_NO):
    min_dist = [[-1]*W for _ in range(H)]
    seen = [[0]*W for _ in range(H)]
    queue = collections.deque() #position[line,Column]Put in
    seen[sh][sw] = 1
    queue.append([sh,sw])
    min_dist[sh][sw] = 0
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or area[nh][nw]=='X':
                continue
            if [nh,nw]==S_factory_point[target_factory_NO]:
                return min_dist[qh][qw]+1
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
for i in range(N):
    sh,sw = S_factory_point[i]
    ans += bfs(sh,sw,i+1)
print(ans)

31 JOI 2012 Qualifying 5-Illuminations

** I couldn't solve it at first sight! !! !! ** ** I couldn't think of the idea of painting this from the outside of the map! Until now, the grid graph problem was only in the four directions of left, right, up, and down, The problem this time is a hexagon, so 6 directions! Looking at the explanation, you can certainly think of the same idea as in 4 directions, and you can think of it as a wall surface that hits a wall!

Also, even if I implemented it after seeing the explanation, the answer did not match the input / output example ... The cause was that we needed a margin of two lines above and below (even lines) instead of a margin of one line above and below! ** ** (Odd and even lines are inconsistent ...)

It was difficult, but it was a good problem! !! !! I learned a lot! !! !!

test.py


import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
W,H = LI()
sub_area = [[0]+LI()+[0] for _ in range(H)]
area = [[0]*(W+2)]+[[0]*(W+2)]+sub_area+[[0]*(W+2)]+[[0]*(W+2)]
dhdw_even = [[-1,0],[-1,1],[0,-1],[0,1],[1,0],[1,1]]
dhdw_odd = [[-1,-1],[-1,0],[0,-1],[0,1],[1,-1],[1,0]]
seen = [[0]*(W+2) for _ in range(H+4)]
queue = collections.deque() #position[line,Column]Put in
def bfs():
    ans = 0
    seen[0][0] = 1
    queue.append([0,0])
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw_even if qh%2==0 else dhdw_odd:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=(H+4)-1) or not(0<=nw<=(W+2)-1) or seen[nh][nw]:
                continue
            if area[nh][nw]==1:
                ans += 1
                continue
            seen[nh][nw] = 1
            queue.append([nh,nw])
    return ans
print(bfs())

32 AOJ 1166 --Maze and Order

** I couldn't solve this at first sight either! !! !! ** **

I did my best while preparing a notebook and a pen, but it was hard! I gave up and saw the code of the person who can do it! IMG_1737.JPG First, ** If it's up or down ** It doesn't move sideways, so you can ignore the vertical wall! ** ** (Similarly for the left and right, ** you can ignore the side walls! **) later, The conditions for checking if there is a wall are different between the top and left and the bottom and right! ** ** ** At the time above, check if there is a wall with the index of nh **, but ** At the bottom, check if there is a wall with the index of nh-1 (original place!) **! (Similarly on the left and right, ** on the right, check if there is a wall with the index of nw-1 (original location!) **!)

was difficult!

test.py


import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
    w,h = LI()
    if w==h==0:
        break
    hwall,wwall = [],[]
    for i in range(2*h-1):
        hwall.append(LI()) if i%2==0 else wwall.append(LI())
    dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
    min_dist = [[-1]*w for _ in range(h)]
    seen = [[0]*w for _ in range(h)]
    queue = collections.deque() #position[line,Column]Put in
    def bfs():
        seen[0][0] = 1
        queue.append([0,0])
        min_dist[0][0] = 1
        while queue:
            qh,qw = queue.popleft()
            for dh,dw in dhdw:
                nh,nw = qh+dh,qw+dw
                if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw]:
                    continue
                if (dh==-1 and wwall[nh][nw]==1) or (dh==1 and wwall[nh-1][nw]==1):
                    continue
                if (dw==-1 and hwall[nh][nw]==1) or (dw==1 and hwall[nh][nw-1]==1):
                    continue
                if [nh,nw]==[h-1,w-1]:
                    return min_dist[qh][qw]+1
                seen[nh][nw] = 1
                queue.append([nh,nw])
                min_dist[nh][nw] = min_dist[qh][qw]+1
    print(bfs() or 0)

Supplement

print(bfs() or 0)

This ʻor will return 0 if the return value is None! (That is, return min_dist [qh] [qw] + 1` did not come back! = Returns 0 if you can't reach the bottom right! )

By the way, it has nothing to do with BFS ** I got stuck in a place where it doesn't matter ** While debugging, the code is supposed to be correct, but it loops infinitely ... The cause is The last seen [nh] [nw] = 1 It was seen [nh] [nw] == 1 and==... It can't be helped, but I killed a lot of time to find this cause. (When I suspected that the condition of the if statement was written incorrectly, the time went by.)

The code is long, so when a bug occurs, it takes time to find out what caused it! But the difficult problem will be more code, ** Don't be discouraged in a place like this! !! !! ** **

33 AtCoder Beginner Contest 088 D - Grid Repainting Difficulty:997 ** This came up with a solution! ** ** All you have to do is implement it!

test.py


import collections,itertools,sys
def S(): return sys.stdin.readline().rstrip()
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
H,W = LI()
s = [S() for _ in range(H)]
black_count = 0
for i,j in itertools.product(range(H),range(W)):
    if s[i][j]=='#':
        black_count += 1
dhdw = [[-1,0],[1,0],[0,-1],[0,1]]
min_dist = [[-1]*W for _ in range(H)]
seen = [[0]*W for _ in range(H)]
queue = collections.deque() #position[line,Column]Put in
def bfs():
    seen[0][0] = 1
    queue.append([0,0])
    min_dist[0][0] = 1
    while queue:
        qh,qw = queue.popleft()
        for dh,dw in dhdw:
            nh,nw = qh+dh,qw+dw
            if not(0<=nh<=H-1) or not(0<=nw<=W-1) or seen[nh][nw] or s[nh][nw]=='#':
                continue
            if [nh,nw]==[H-1,W-1]:
                return min_dist[qh][qw]+1
            seen[nh][nw] = 1
            queue.append([nh,nw])
            min_dist[nh][nw] = min_dist[qh][qw]+1
    else:
        return -1
min_dist = bfs()
print(H*W-black_count-min_dist if min_dist!=-1 else -1)

Next time, I will solve the following 12 questions!

Dynamic programming: Knapsack DP 34 ALDS_10_A --Fibonacci number super basic. You can feel "what is DP". 35 DPL_1_B --0,1 Knapsack problem This is a basic problem. 36 DPL_1_C --Knapsack problem This is a basic problem. 37 DPL_1_A --Coin problem This is a basic problem. 38 ALDS_10_C --The longest common subsequence is a basic problem.

(From here on, I won't write what kind of DP can be solved, but all can be solved with Knapsack DP or its variants.)

39 JOI 2011 Qualifying 4-1st grade 40 JOI 2012 Qualifying 4-Pasta 41 JOI 2013 Qualifying 4-Hot days 42 JOI 2015 Qualifying 4-Silk Road 43 Pa Lab Cup 2019 D --Pa Lab Flag 44 AOJ 1167 --Polock forecast 45 AOJ 2199 --Differential pulse code modulation

Part7/22 end!

Next (Part 8/22)

Recommended Posts

[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
I tried to solve the ant book beginner's edition with python
Python that I would like to recommend to programming beginners
I tried to solve the soma cube with python
I tried to solve the problem with Python Vol.1
I tried to solve AOJ's number theory with Python
I tried to enumerate the differences between java and python
I tried to make GUI tic-tac-toe with Python and Tkinter
A super introduction to Django by Python beginners! Part 6 I tried to implement the login function
I tried to summarize the languages that beginners should learn from now on by purpose
Tohoku University 2020 First semester math exam (science) I tried to solve major questions 1 to 3 with Python
A super introduction to Django by Python beginners! Part 1 I tried to display an HTML page that only says "Hello World"
I tried to touch Python (installation)
python beginners tried to find out
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
[Python] A memo that I tried to get started with asyncio
[Pandas] I tried to analyze sales data with Python [For beginners]
I tried to make a periodical process with Selenium and Python
I tried to easily detect facial landmarks with python and dlib
[Python] I tried to explain words that are difficult for beginners to understand in an easy-to-understand manner.
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to refer to the fun rock-paper-scissors poi for beginners with Python
I tried to implement permutation in Python
A super introduction to Django by Python beginners! Part 3 I tried using the template file inheritance function
How to write offline real time I tried to solve E11 with python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I wanted to solve ABC160 with Python
I tried using PyEZ and JSNAPy. Part 2: I tried using PyEZ
I tried to implement ADALINE in Python
I tried to let optuna solve Sudoku
I tried to develop a Formatter that outputs Python logs in JSON
A super introduction to Django by Python beginners! Part 2 I tried using the convenient functions of the template
I tried to make Kana's handwriting recognition Part 2/3 Data creation and learning
I wanted to solve ABC159 in Python
I tried to implement PPO in Python
10 Python errors that are common to beginners
I tried to verify and analyze the acceleration of Python by Cython
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
I tried to solve TSP with QAOA
[Python] I tried to calculate TF-IDF steadily
[Markov chain] I tried to read quotes and negative emotions into Python.
I tried to touch Python (basic syntax)
I tried to create a sample to access Salesforce using Python and Bottle