[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!

For example, let's say you have a 4 * 4 figure like this. スクリーンショット 2020-03-25 0.09.55.png

For the time being, paint black and white. スクリーンショット 2020-03-25 0.10.38.png

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 ... スクリーンショット 2020-03-25 0.25.02.png

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.

スクリーンショット 2020-03-25 0.28.07.png The color has changed!

With this, "operation" is done once!

Then, there is a route that allows you to go to the lower right without any operation! スクリーンショット 2020-03-25 0.29.18.png 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!

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!

Recommended Posts

[Python] AGC043A (Problem reading comprehension and DP) [At Coder]
[Python] ABC133B (upper right triangle problem) [At Coder]
[At Coder] Solving a typical BFS problem [A --Darker and Darker]
[Python] Competitive template [At Coder]
Python CSV file reading and writing
Reading and writing NetCDF with Python
[At Coder] ABC085C --Otoshidama's Python answer
Reading and writing CSV with Python
Reading and writing text in Python
Python comprehension (list and generator expressions) [additional]
Reading and writing JSON files with Python
(Python) HTML reading and regular expression notes
Python comprehension
Python comprehension
At Coder (2020/09/08)
[At Coder] Beginner Contest 175 ABCD python Solution introduction
Python3 Engineer Certification Basic Exam-Notes and Problem Trends-
Study from Python Reading and writing Hour9 files
Reading and writing CSV and JSON files in Python
[At Coder] Solve the problem of binary search
Reading and writing fits files with Python (memo)
Example of reading and writing CSV with Python
[Python] ABC159D (High School Mathematics nCr) [At Coder]