Article From:https://www.cnblogs.com/acgoto/p/9972613.html

A.Land, color, magic

Title Description

       Now, as a new star, Peng Luoke, you have found an excellent place to practice. This area can be described as an n x m rectangle. You’ve marked some places in the field. Next, it’s time to give you colour to the whole land. A position can be given your color whenAnd only if one of the following conditions is satisfied:
       1. This position is marked.
       2. This position is disconnected from the boundary without being marked.Four Unicom). In other words, if you start from this location and can never reach the boundary of the map without going through the marked position and moving only up, down, left and right directions, then the location is eligible.
       Now, your friends want to know, how many places can you give your own color?

Input Description:

The first line contains two positive integers n, m, representing the length and width of the map.
Next, n rows, each with a string of m, represent one line of the map.
Where'. 'means that the location is not marked; and'#' means that the location is marked. Make sure that the map consists of'. 'and'#'.

Output description:

The output is a single line and contains an integer to represent your answer.

Example 1

input

4 4
....
.###
.#.#
.###

output

9

Explain

The position where the color can be assigned is used in the following figure. Marked out.
\texttt{....}
\texttt{.@@@}
\texttt{.@@@}
\texttt{.@@@}

Remarks:

1 ≤ n x m ≤ 10^6.
problem-solving ideas: the meaning of the problem is that the current coordinates are not marked as'.', if it can reach any boundary around along the'.', then it can not be marked as'#', otherwise it can be marked as' #', ask the final number of marked.。 Obviously, we only need to do DFS once for each coordinate point around the boundary, and record the total distance of each'. 'in the boundary, then the final answer is n*m-step. Another point is to use vector to store maps to avoid hypermemory.
AC code:
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn=1e6+5;
 5 int n,m,step;bool vis[maxn];
 6 vector<string> vec;string str;
 7 int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
 8 void dfs(int a,int b){
 9     if(a<0||b<0||a>=n||b>=m||vis[a*m+b]||vec[a][b]=='#')return;
10     vis[a*m+b]=true,step++,vec[a][b]='#';
11     for(int i=0;i<4;++i)dfs(a+dir[i][0],b+dir[i][1]);
12 }
13 int main(){
14     while(cin>>n>>m){
15         vec.clear(),step=0;memset(vis,false,sizeof(vis));
16         for(int i=0;i<n;++i)cin>>str,vec.push_back(str);
17         for(int j=0;j<m;++j){
18             if(vec[0][j]=='.')dfs(0,j);
19             if(vec[n-1][j]=='.')dfs(n-1,j);
20         }
21         for(int i=1;i<n-1;++i){
22             if(vec[i][0]=='.')dfs(i,0);
23             if(vec[i][m-1]=='.')dfs(i,m-1);
24         }
25         cout<<n*m-step<<endl;
26     }
27     return 0;
28 }

B.Zandika Voice Nisa and Ozaki

Title Description

       The Orzac Legion is coming! Zandika is in crisis! The endless reincarnation of Tungsten Ramo and the Truth Butcher Kokirai led this huge group of predators to vandalism in Zandika. Travel Master Nissa Revan has to stop all this.
       In the corner of Zandika, there are n Korean tribes. These tribes are closely related to each other in order to resist the attack of Ozaki. There is a direct link between any two tribes. In other words, the N tribes and several roads form a complete picture.
       Now, the Ozaki Legion has occupied the No. 1 Korean tribe and stayed there. But Tungsten Ramo and Kokirai started the game. The rules of the game are as follows: Tungsten Ramo and Kokirai take turns to lead the Ozaki Legion to move once. Every time you can get from a Korean tribeMove to another Korean tribe through an uncorrupted road. Any movement must take place in these n Korean tribes and their roads. Ozaki’s swallowing of magic will corrode the way Ozaki’s Legion travels. Finally, under the restrictions of the rules, the Ozaki Legion will have no way to go. At this point,The King of Ozaki, who will lead the Legion in its next move, will lose the game. Tungsten Lamo first.
       As two of the three ancestors of Ozaki, Tungsten Ramo and Kokira naturally possess super intelligence. So you can assume that they will all play with the best decisions.
       The winner of the game will lead the army to fight Nisa, who is still on her way. So please watch the game first, and then you can tell Nissa who will be her opponent.

Input Description:

There are many groups of test data in this question.
The first line is a positive integer T, representing the number of data groups.
Next, line T, n for each line, indicates the number of Kou tribes.

Output description:

The output is a total of T lines, with a string of "Ulamog, the Infinite Gyre" or "Kozilek, Butcher of Truth" representing the winner (parentheses removed). The former is infinite reincarnated tungsten ramo, the latter is infinite reincarnated tungsten ramo.Truth butcher Kokira.

Example 1

input

2
1
3

output

Kozilek, Butcher of Truth
Ulamog, the Infinite Gyre

Explain

– When n = 3, Tungsten Ramo can lead the regiment from 1 to 2, and then The edge can’t go any further.
– Next, Kokira can only lead the Legion to move to 3, after that. The edge can’t go any further.
– In the end, as long as Tungsten Ramo returned the regiment to 1, Kokirai would have no way to go.

Remarks:

1 ≤ T ≤ 2000
1 ≤ n ≤ 2000
problem-solving ideas: enumeration + verification, enumeration of the first few n can be found, only when n = 1, the first hand will fail, the rest of the case is the first hand will win, validation handed in an AC.
AC code:
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int T,n;
 4 int main(){
 5     while(cin>>T){
 6         while(T--){
 7             cin>>n;
 8             if(n==1)cout<<"Kozilek, Butcher of Truth"<<endl;
 9             else cout<<"Ulamog, the Infinite Gyre"<<endl;
10         }
11     }
12     return 0;
13 }
Link of this Article: Cowboy Practice Competition 31

Leave a Reply

Your email address will not be published. Required fields are marked *