|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||128 MB||7||3||3||42.857%|
The disease is spreading quickly, and the government has requested a map of infected regions. They would like to see what certain regions would look like, worst-case scenario, given some series of events. There are four stages of infection that the feds are interested in.
An infection event is anything that causes a zone to advance towards a higher stage of infection. This is usually the result of a quarantine breach, virus mutation, or biological terrorism. When an infection event occurs in a zone, it will, worst-cast scenario, cause the zone to advance in stage. A zone in stage D cannot advance in stage any further and will, worst-case scenario, result in an outbreak for each additional infection event it experiences. When an outbreak occurs, all neighboring zones experience an additional infection event. An outbreak can cause a chain reaction of outbreaks, but an outbreak can only cause a maximum of one outbreak in each zone.
Zones marked with an X character are impassible and unpopulated areas that cannot become infected. An adjacent zone is one zone above, below, to the left, or to the right on the grid of zones. During an outbreak, the infection cannot spread diagonally.
You will receive a grid of zones with their starting stages and a sequence of infection events with the coordinates of the zones in which they occur. Each infection event should be processed before calculating the result of the next infection event.
The first line of input will contain the number of test cases, N (1 <= N <= 50). Each test case will begin with a line giving the width, W (1 <= W <= 100) and height, H (1 <= H <= 100) of the grid, followed by the grid itself. Each zone in the grid will be marked by the stage that the zone is currently in, or the character X if the zone is impassable.
Following the grid will be a line with the number of infection events I (0 <= I <= 1000). I lines will follow each giving an X and Y coordinate of a zone. Each line represents an infection event that occurs on the Xth column (the left most column being X = 0) and the Yth row (the top row being Y = 0).
Your output should show each grid with its states if the worst-case scenario occurs.
2 3 4 AAA AXA XAA AAA 5 1 2 2 2 1 2 1 2 1 2 7 6 AAAAAAA AAAAADA AAXAAAA AAAXDAA AAXXAAB AAXXACD 10 6 4 4 4 4 4 6 3 4 3 6 4 6 2 6 4 6 4 6 4
AAA AXA XDC ABA AAAAAAA AAAAADA AAXACBC AAAXDDD AAXXDDD AAXXDDD