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
Top