SHARE
TWEET

Lab Alg Avançados Contest 2 - Exercício D

a guest Aug 12th, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct state{
  6.     char digit[4];
  7.     int depth;
  8. };
  9.  
  10. char moves[8][4] = {{-1,  0,  0,  0},
  11.                     { 1,  0,  0,  0},
  12.                     { 0, -1,  0,  0},
  13.                     { 0,  1,  0,  0},
  14.                     { 0,  0, -1,  0},
  15.                     { 0,  0,  1,  0},
  16.                     { 0,  0,  0, -1},
  17.                     { 0,  0,  0,  1}};
  18.  
  19. void next_states(state s, state nexts[8]){
  20.     int i, j;
  21.  
  22.     for (i = 0; i < 8; i++){
  23.         nexts[i] = s;
  24.         nexts[i].depth = s.depth + 1;
  25.         for (j = 0; j < 4; j++){
  26.             nexts[i].digit[j] += moves[i][j];
  27.             if (nexts[i].digit[j] < 0)
  28.                 nexts[i].digit[j] = 9;
  29.             if (nexts[i].digit[j] > 9)
  30.                 nexts[i].digit[j] = 0;
  31.         }
  32.     }
  33. }
  34.  
  35. int equal(state s, state e){
  36.     int i;
  37.  
  38.     for (i = 0; i < 4; i++){
  39.         if (s.digit[i] != e.digit[i])
  40.             return 0;
  41.     }
  42.     return 1;
  43. }
  44.  
  45. int bfs(state current, state final, int visited[10][10][10][10]){
  46.     state nexts[8];
  47.     int i;
  48.     queue<state> q;
  49.  
  50.     if (!visited[current.digit[0]][current.digit[1]][current.digit[2]][current.digit[3]]){
  51.         visited[current.digit[0]][current.digit[1]][current.digit[2]][current.digit[3]] = 1;
  52.         q.push(current);
  53.         while(!q.empty()){
  54.             current = q.front();
  55.             q.pop();
  56.             if (equal(current, final)) return current.depth;
  57.             next_states(current, nexts);
  58.             for (i = 0; i < 8; i++){
  59.                 if(!visited[nexts[i].digit[0]][nexts[i].digit[1]][nexts[i].digit[2]][nexts[i].digit[3]]){
  60.                     visited[nexts[i].digit[0]][nexts[i].digit[1]][nexts[i].digit[2]][nexts[i].digit[3]] = 1;
  61.                     q.push(nexts[i]);
  62.                 }
  63.             }
  64.         }
  65.     }
  66.     return -1;
  67. }
  68.  
  69. int main(void){
  70.     int nr_tests, test, forbidden, i, j, k, l;
  71.     int visited[10][10][10][10];
  72.     state initial, final, aux;
  73.  
  74.     scanf("%d", &nr_tests);
  75.     for (test = 0; test < nr_tests; test++){
  76.         scanf("%d %d %d %d", &initial.digit[0], &initial.digit[1], &initial.digit[2], &initial.digit[3]);
  77.         scanf("%d %d %d %d", &final.digit[0], &final.digit[1], &final.digit[2], &final.digit[3]);
  78.         scanf("%d", &forbidden);
  79.         for (i = 0; i < 10; i++){
  80.             for (j = 0; j < 10; j++){
  81.                 for (k = 0; k < 10; k++){
  82.                     for (l = 10; l < 10; l++){
  83.                         visited[i][j][k][l] = 0;
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.         for (i = 0; i < forbidden; i++){
  89.             scanf("%d %d %d %d", &aux.digit[0], &aux.digit[1], &aux.digit[2], &aux.digit[3]);
  90.             visited[aux.digit[0]][aux.digit[1]][aux.digit[2]][aux.digit[3]] = 1;
  91.         }
  92.         initial.depth = 0;
  93.         printf("%d\n", bfs(initial, final, visited));
  94.     }  
  95.     return 0;
  96. }
RAW Paste Data
Top