• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 23rd, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2.
3. #include <stdio.h>
4. #include <stdlib.h>
5. #include <stdbool.h>
6.
7. int arr[21][21] = {0,};         // μ²μ μλ ₯λ°μ Map λ°°μ΄(λ°λν)
8. int cal[21][21] = {0,};         // λ°λ‘ μ°©μλ₯Ό νλ €λ Map λ°°μ΄(λ°λν)
9. bool queCheck[21][21] = {false,};   // DFSλ‘ μ§κΈ μμΉμ νλμ΄ μ΄μμλ νλμΈμ§ μ£½μ΄μλ νλμΈμ§ νλ¨ν  λ μ¬μ©ν  λ°°μ΄
10. bool Catch[21][21] = {false,};      // κΈ°λ³Έμ μΌλ‘ falseλ‘ μ΄κΈ°ννκ³  νλ μμΉμΈλ° falseλ©΄ μ΄μμλ νλ, trueλ©΄ μ£½μ νλ, μ°λ¦¬κ° μ μλ‘ κ³μ°ν  νλμ΄λΌλ λ»
11. int dir_x[4] = {-1, 0, 1, 0};       // μ, ν, μ’, μ° κ³μ°νλ €κ³  λ§λ¬.
12. int dir_y[4] = {0, 1, 0, -1};
13.
14. bool check(int x, int y, int N, int M){ // ν΄λΉ ν¬μ§μμ΄ λ°μ΄λλ¦¬λ₯Ό λμ΄κ°λμ§ μ λμ΄ κ°λμ§ μ²΄ν¬νλ ν¨μ
15.     if( x<0 || y<0 || x>=N || y>=M ){
16.         return false;
17.     }else{
18.         return true;
19.     }
20. }
21.
22. void Dfs(int x, int y, int N, int M){   // ν΄λΉ νλμ΄ μ΄μμλμ§ μ μ΄μμλμ§ μΈμ ν λͺ¨λ  νλμ μνλ₯Ό μ²΄ν¬ν΄λ³΄κ³  μ§κΈ μμ μ νλμ μνλ₯Ό νλ³ν  μ μλ€.
23.                     // ν΄λΉ κ·Έλ£Ήμ λ¨ νλμ νλμ΄λΌλ μ΄μμμΌλ©΄ κ·Έ κ·Έλ£Ή μ μ²΄μ νλμ μ΄μμλ€.
24.     int i;
25.     int dx, dy;
26.     bool flag = false;
27.
28.     queCheck[x][y] = true;      // DFSν λ visited[v]νλ λ°°μ΄μ²λΌ
29.     for(i=0;i<4;i++){
30.         dx = x+dir_x[i];
31.         dy = y+dir_y[i];
32.         if(check(dx, dy, N, M)){    // ν΄λΉ μ’νκ° λ°λνμ λ²μ΄λμ§ μμΌλ©΄μ,
33.         // μ§κΈ μ΄ νλκ³Ό μ,ν,μ’,μ°λ‘ μ°κ²°λ μ΄λ ν νλμ΄λΌλ μ΄μμμΌλ©΄ λλ¨Έμ§ λ°©ν₯μ κ²μ¬ν  νμλ μμ. μ΄μμμμ΄ λ³΄μ₯λκΈ° λλ¬Έμ.
34.             if(cal[dx][dy] == 2 && Catch[dx][dy] == false && queCheck[dx][dy] == false){
35.                 flag = true;
36.                 break;
37.             }else;
38.         }else;
39.     }
40.
41.     if(flag == true){   // μ΄ λμ μ΄μμμ.
42.         Catch[x][y] = false;
43.         return ;
44.     }
45.
46.     for(i=0;i<4;i++){   // μ§κΈ μ΄ λμ΄ μ£½μλμ§ μ΄μλμ§ μ ννκ² λͺ°λΌ == λΉ κ³΅κ°κ³Ό μΈμ νμ§ μκ³  νλκ³Ό μΈμ ν κ²½μ°, μΈμ ν νλλ κ²μ¬ν΄μΌλ.
47.         dx = x+dir_x[i];
48.         dy = y+dir_y[i];
49.         if(check(dx, dy, N, M)){    // λ°λν μ’ν λ΄μ μ‘΄μ¬νκ³ , μΈμ ν νλμ΄κ³ , κ·Έ μΈμ ν νλμ΄ μμ§ κ²μ¬νμ§ μμ μνλ©΄ κ²μ¬.
50.             if(cal[dx][dy] == 2 && Catch[dx][dy] == true && queCheck[dx][dy] == false){
51.                 Dfs(dx, dy, N, M);
52.             }else;
53.         }else;
54.     }
55. }
56.
57. int main()
58. {
59.     bool flag = true;
60.     int N, M;
61.     int i, j, k, l, m;
62.     int dx, dy;
63.     int cnt = 0;        // κ²μν  μ’νκ° λͺ κ°μΈμ§
64.     int sum = 0;        // μ°©μν Caseλ§λ€ μ‘μ μ μλ νλμ μ΅λ κ°μ
65.     int max = 0;        // μ λ΅
66.     int pos[2][1601] = {0,};    // λ°νμμλ¬κ° λ°μνλ μ΄μ , μ°λ¦¬κ° μ°©μν  μ μλ λͺ¨λ  μ’νλ₯Ό μ¬κΈ°μ λ΄μΌλ €κ³  νλλ° κ΅¬νλ κ³Όμ μμ μ€λ³΅μ΄ ν¬ν¨λκ² μ€μ ν΄λ¨λ€. κ·Έλμ 401κ°μμ μ»€λ²κ° λλ κ²μ΄ μλλΌ 1601κ° κΉμ§ ν λΉνμ.
67.
68.     // μ΄κΈ°ν
69.     for(i=0;i<20;i++){
70.         for(j=0;j<20;j++){
71.             arr[i][j] = 0;
72.             cal[i][j] = 0;
73.             Catch[i][j] = false;
74.             queCheck[i][j] = false;
75.         }
76.     }
77.
78.     for(i=0;i<2;i++){
79.         for(j=0;j<1601;j++){    // μ λ΅ μ μΆνμλ 401λ‘ ν΄μ ν΅κ³ΌλμΌλ μ ννλ 1601λ‘ λ°κΏμ€μΌ μ°λ κΈ°κ°μ λλΉν  μ μμ.
80.             pos[i][j] = 0;
81.         }
82.     }
83.
84.     scanf("%d %d", &N, &M);
85.     for(i=0;i<N;i++){
86.         for(j=0;j<M;j++){
87.             scanf("%d", &arr[i][j]);
88.             cal[i][j] = arr[i][j];
89.         }
90.     }
91.
92.     dx = 0;
93.     dy = 0;
94.     for(i=0;i<N;i++){
95.         for(j=0;j<M;j++){
96.             if(arr[i][j] == 2){         // λ°λνμμ νλμ μ°Ύμμ.
97.                 for(k=0;k<4;k++){
98.                     dx = i+dir_x[k];
99.                     dy = j+dir_y[k];
100.                     if(check(dx, dy, N, M)){
101.                         if(arr[dx][dy] == 0){   // κ·Έ νλκ³Ό μ, ν, μ’, μ°λ‘ μΈμ ν λΉ κ³΅κ°(0)μ μ°Ύμ == μ°λ¦¬κ° μ°©μν  κ°λ₯μ±μ΄ μλ κ³΅κ°
102.                             pos[0][cnt] = dx;   // κ°μ μ’νκ° μ,ν,μ’,μ°μ κ²μ¬νλ©΄μ μ΅λ 4λ²κΉμ§ μ€λ³΅λ  μ μκΈ° λλ¬Έμ, 3λ²λ¬Έμ κ° 1000X1000μ¬μ΄μ¦ λ°λνμ΄λκΉ μ€λ³΅μ²λ¦¬λ₯Ό ν΄μ€μΌ λ  λ―.
103.                             pos[1][cnt] = dy;
104.                             cnt++;
105.                         }else;
106.                     }else;
107.                 }
108.             }
109.         }
110.     }
111.     dx = dy = 0;
112.     for(i=0;i<cnt-1;i++){
113.         for(j=i+1;j<cnt;j++){
114.             cal[pos[0][i]][pos[1][i]] = 1;  // κ°λ₯ν μ’νμ λ νλλ₯Ό μ°©μν¨.
115.             cal[pos[0][j]][pos[1][j]] = 1;  // κ°λ₯ν μ’νμ λ νλλ₯Ό μ°©μν¨.
116.             for(k=0;k<N;k++){
117.                 for(l=0;l<M;l++){
118.                     if(cal[k][l] == 2){     // νλμ λ°κ²¬νλ€.
119.                         flag = true;
120.                         for(m=0;m<4;m++){
121.                             dx = k+dir_x[m];
122.                             dy = l+dir_y[m];
123.                             if(check(dx, dy, N, M)){
124.                                 if(cal[dx][dy] == 0){   // κ·Έ νλ κ·Όμ²μ λΉ κ³΅κ°μ΄ μλ€ == κ·Έ νλμ μ΄μλ€. == λ€λ₯Έ μ’ν κ²μ¬ν  νμμμ΄ μ΄ νλμ μ΄μμμμ΄ λ³΄μ₯λλ€.
125.                                     flag = false;
126.                                 }else;
127.
128.                             }else;
129.                             if(!flag){
130.                                 Catch[k][l] = false;    // μ΄ νλμ μ΄μμλ€. μ‘μλ¨Ήμ μ μλ νλμ΄λ€.
131.                                 break;
132.                             }
133.                         }
134.                         if(flag){           // μ,ν,μ’,μ°λ₯Ό λ€ κ²μ¬ν΄λ΄€λλ° μΈμ ν λΉ κ³΅κ°μ΄ μλ€. μ΄ νλμ μ£½μ΄μλ€. λ¨Ήμ μ μλ νλμ΄λ€.
135.                             Catch[k][l] = true;
136.                         }
137.                     }
138.                 }
139.             }
140.
141.         // μ΄κΈ°ν
142.             for(k=0;k<N;k++){
143.                 for(l=0;l<M;l++){
144.                     queCheck[k][l] = false;
145.                 }
146.             }
147.
148.             flag = true;
149.             for(k=0;k<N;k++){
150.                 for(l=0;l<M;l++){
151.                     if(Catch[k][l] == true && cal[k][l] == 2){  // μμμ 1μ°¨μ μΌλ‘ κ²μ¬νμ λ μΈμ ν μ,ν,μ’,μ°κ° λΉ κ³΅κ°μ΄ μλ, μλλ₯Ό κΈ°μ€μΌλ‘ μ΄μμλ μ£½μ΄μλλ₯Ό νλ¨νμ.
152.                         Dfs(k, l, N, M);            // μμμ  μΈμ ν λμ΄ νλμΈ κ²½μ°μ κ·Έ νλμ΄ μ΄μμλμ§ μ£½μ΄μλμ§μ λ°λΌ μ΄ λμ΄ μ΄μμλ μ£½μ΄μλλ₯Ό μ μ μλλ°, μΈμ ν λͺ¨λ  νλμ κ²μ¬ν΄μΌ νκΈ° λλ¬Έμ DFSμ¬μ©
153.                         for(m=0;m<4;m++){           // DFS λλκ³  λ§¨ μ²μ DFS νΈμΆνλ κ·Έ μμΉλ μ΅μ νλ₯Ό ν΄μ€μΌ λμ ν λ² λ λλ €μ€ -> κ΅¬νλ¬Έμ μ
154.                             dx = k+dir_x[m];
155.                             dy = l+dir_y[m];
156.                             if(check(dx, dy, N, M)){
157.                                 if(cal[dx][dy] == 2 && Catch[dx][dy] == false){
158.                                     flag = false;
159.                                 }else;
160.                             }else;
161.                         }
162.                         if(flag == false){
163.                             Catch[k][l] = false;
164.                         }
165.                     }
166.                     flag = true;
167.                 }
168.             }
169.
170.             sum = 0;
171.             for(k=0;k<N;k++){
172.                 for(l=0;l<M;l++){
173.                     if(Catch[k][l] == true){    // μ‘μ λ¨Ήμ μ μλ λμ κ°μ κ³μ°
174.                         sum++;
175.                     }
176.                 }
177.             }
178.
179.         // μ΄κΈ°ν
180.             for(k=0;k<N;k++){
181.                 for(l=0;l<M;l++){
182.                     Catch[k][l] = false;
183.                     queCheck[k][l] = false;
184.                 }
185.             }
186.             max = max>sum?max:sum;
187.             sum = 0;
188.             cal[pos[0][i]][pos[1][i]] = 0;
189.             cal[pos[0][j]][pos[1][j]] = 0;
190.         }
191.     }
192.     printf("%d", max);
193.     return 0;
194. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?