• API
• FAQ
• Tools
• Archive
daily pastebin goal
79%
SHARE
TWEET

# Untitled

a guest Aug 12th, 2017 46 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cstdio>
2.
3. struct node { // Store two coordinates
4.     int row;
5.     int col;
6. };
7.
8. int
9.     arr[100][100], // The input matrix
10.     n, m; // Matrix size
11.
12. node
13.     prev[100][100], // Store previous vertices
14.     knight[100]; // Store knights' coordinates
15.
16. bool
17.     visited[100][100], // Store visited vertices
18.     found; // Flag if Eli was found
19.
20.
21. void dfs(int i, int j) { // Depth-first search
22.     if (found)
23.         return;
24.
25.     if ( arr[i][j] == 'E' ) { // Eli was found
26.         found = true;
27.         return;
28.     }
29.     visited[i][j] = true;
30.     if ( !visited[i][j-1] && j-1 >= 0 && arr[i][j-1] != '#' ) { // Go left
31.         //printf("left\n");
32.         prev[i][j-1].row = i;
33.         prev[i][j-1].col = j;
34.         dfs(i, j-1);
35.     }
36.     if ( !visited[i][j+1] && j+1 < m && arr[i][j+1] != '#' ) { // Go right
37.         //printf("right\n");
38.         prev[i][j+1].row = i;
39.         prev[i][j+1].col = j;
40.         dfs(i, j+1);
41.     }
42.     if ( !visited[i+1][j] && i+1 < n && arr[i+1][j] != '#' ) { // Go down
43.         //printf("down\n");
44.         prev[i+1][j].row = i;
45.         prev[i+1][j].col = j;
46.         dfs(i+1, j);
47.     }
48.     if ( !visited[i-1][j] && i-1 >= 0 && arr[i-1][j] != '#' ) { // Go up
49.         //printf("up\n");
50.         prev[i-1][j].row = i;
51.         prev[i-1][j].col = j;
52.         dfs(i-1, j);
53.     }
54. }
55.
56.
57. int main() {
58.     node eli; // Store Eli's coordinates
59.     knight[0].row = 0; // Store number of knights
60.     int result = 0;
61.     char c;
62.
63.     // Prepare input data
64.     scanf("%d %d", &n, &m);
65.     for (int i = 0; i < n; i++) {
66.         for (int j = 0; j < m; j++) {
67.             scanf("%c", &c);
68.             if (c != '\n') {
69.                 arr[i][j] = c;
70.                 if (c == 'E') { // If it's Eli, save her coordinates
71.                     eli.row = i;
72.                     eli.col = j;
73.                 }
74.                 if (c == 'K') { // If it's a knight, save his coordinates
75.                     knight[++(knight[0].row)].row = i;
76.                     knight[knight[0].row].col = j;
77.                 }
78.             } else { // If it's a new line
79.                 j--;
80.             }
81.         }
82.     }
83.
84.     // Sum knights' paths to Eli
85.     for (int i = 1; i <= knight[0].row; i++) {
86.         // Resets
87.         for (int j = 0; j < n; j++) {
88.             for (int k = 0; k < m; k++) {
89.                 visited[j][k] = false;
90.                 prev[j][k].row = prev[j][k].col = -1;
91.             }
92.         }
93.         found = false;
94.
95.         // dfs the knight
96.         dfs(knight[i].row, knight[i].col);
97.
98.         if (found) {
99.             node trace = eli;
100.             while (trace.row != -1 && trace.col != -1) {
101.                 result++;
102.                 trace = prev[trace.row][trace.col];
103.             }
104.             result--;
105.         }
106.     }
107.
108.     if (result != 0)
109.         printf("%d\n", result);
110.     else
111.         printf("%d\n", -1);
112.
113.     return 0;
114. }
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.

Top