** 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! 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)