[Python] AGC043A (Problem reading comprehension and DP) [At Coder]

Let's read and understand the problem! Don't give up immediately if you encounter a difficult problem statement!

AGC043A Difficulty:803 Strong enemy! But if you clear the following two points, this problem will be solved! ① Problem reading comprehension ② DP (Dynamic Programming)

① Problem reading comprehension

The latter half of the problem statement, "the following operations," didn't come to my mind at all! Here, we will decipher "the following operations". Quote the part of "the following operation" from the problem

Choose four integers r0, c0, r1, c1 (1 ≤ r0 ≤ r1 ≤ H, 1 ≤ c0 ≤ c1 ≤ W). Change the color of (r, c) for all r, c that satisfy r0 ≤ r ≤ r1, c0 ≤ c ≤ c1. That is, if it is white, it is black, and if it is black, it is white.

？？？

Never give up! Let's consider a concrete example for the time being! Prepare a notebook and pen!

• Notebooks and pens are essential for competition pros! From [Python] ABC159D (High School Mathematics nCr) [At Coder]

For example, let's say you have a 4 * 4 figure like this.

For the time being, paint black and white.

The upper left (0,0) is the start and the lower right (3,3) is the goal. You can only go right or down as a route on the way! White is the road. Black feels like an obstacle. I'm wondering whether to go right or left from now (0,0)! Here comes the "operation below"!

Choose four integers r0, c0, r1, c1 (1 ≤ r0 ≤ r1 ≤ H, 1 ≤ c0 ≤ c1 ≤ W).

It seems that r0, c0, r1, c1 (r is row, c is column) can be selected as you like (arbitrarily) under the above conditions. r0,c0,r1,c1 = 1,0,3,2 *** r, c is 1 or more (upper left (1,1) start in the question sentence), but note that my image starts at the upper left (0,0) due to the index. ** ** If you try ...

Change the color of (r, c) for all r, c that satisfy r0 ≤ r ≤ r1, c0 ≤ c ≤ c1. That is, if it is white, it is black, and if it is black, it is white.

With this, "operation" is done once!

Then, there is a route that allows you to go to the lower right without any operation! Therefore, the correct answer to this question is "1" times.

** What you can see from here is that if black (like an obstacle) is connected, it can be changed to white (road) with one "operation"! ** **

about it!

Once you understand this, all you have to do is implement the program!

As a bonus, it's a chat, In order to be able to understand (decipher) the problem quickly and accurately in the actual contest It is necessary to improve reading comprehension. I personally think that there are two ways to improve reading comprehension.

--A: Solve many difficult problems in Japanese (become able to solve similar patterns) ――B: When you encounter a difficult problem in Japanese, get into the habit of thinking with a notebook and pen without looking at the explanation (without running away) (you can only learn it in actual battles)

② DP (Dynamic Programming)

① was long, If you understand the contents of ① and then understand the basics of DP, you should be able to solve this problem!

• The standard in me for "Basics of DP" is whether the following two Kaeru-kun problems can be solved.

• Frog1
• Frog2

Conceptually

--Think the first row and the first column separately (in my image, the initial value of dpmap is set) ――From the 2nd row and 2nd column onward, it feels like putting the pattern that came from the top and the pattern that came from the left with the smaller number of operations into the dpmap of the two-dimensional array. --The final answer is the lower right of dpmap (dpmap [-1] [-1])

①+②

In summary, it looks like this.

test.py

def LI(): return list(map(int,input().split()))
H,W = LI()
S = [input() for _ in range(H)]
dp = [[-1]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        judge = 1 if S[i][j]=='#' else 0
        if i==0: #Line 0
            if j==0:
                dp[0][0] = judge
            else:
                dp[0][j] = dp[0][j-1]+judge*(0 if S[0][j-1]=='#' else 1)
        else: #Other than line 0
            if j==0:
                dp[i][0] = dp[i-1][0]+judge*(0 if S[i-1][0]=='#' else 1)
            else:
                temp1 = dp[i][j-1]+judge*(0 if S[i][j-1]=='#' else 1)
                temp2 = dp[i-1][j]+judge*(0 if S[i-1][j]=='#' else 1)
                dp[i][j] = min(temp1,temp2)
print(dp[-1][-1])

This problem is not so difficult for the algorithm itself (it's just a two-dimensional array, which is the basic level of DP), The problem statement is difficult and the difficulty is rising. To put it the other way around, if you can improve your reading comprehension, the rate will rise at once! !! !! Good luck!

end!