Untitled

 avatar
unknown
plain_text
a year ago
3.7 kB
7
Indexable
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoDiTau {
  public static int N, demLeft, demRight, move, res;
  public static int[] arr, gate, numOfPerson, visited, visited2;

  public static void demViTriGanNhat(int gate) {
    // dem trai
    int left = gate;
    int right = gate;
    demLeft = 0;
    demRight = 0;
    
    while(left >= 0) {
      demLeft++;
      if (visited[left] == 0) {
        break;
      }
      left--;
    }
    
    // dem phai
    while (right < N) {
      demRight++;
      if (visited[right] == 0) {
        break;
      }
      right++;
    }
    
    if (left == -1) {
      demLeft = Integer.MAX_VALUE;
    }
    
    if (right == N) {
      demRight = Integer.MAX_VALUE;
    }
  }
  
  public static void backtrack() {
    if (visited2[0] == 1 && visited2[1] == 1 && visited2[2] == 1) {
      if (res > move) {
        res = move;
      }
      return;
    }
    
    for (int j = 0; j < 3; j++) {
      int currentGate = gate[j];
      if (visited2[j] == 0) {
        visited2[j] = 1;
        
        int person = numOfPerson[j];
        int tot = 0;
        while (person != 1) {
          demViTriGanNhat(currentGate);
          if (demLeft <= demRight) {
            visited[currentGate-demLeft+1] = j+1;
            person--;
            move+=demLeft;
            tot += demLeft;
          }
          else {
            visited[currentGate+demRight-1] = j+1;
            person--;
            move+=demRight;
            tot += demRight;
          }
        }
        demViTriGanNhat(currentGate);
        if (demLeft < demRight) {
          visited[currentGate-demLeft+1] = j+1;
          person--;
          move+=demLeft;
          backtrack();
          visited[currentGate-demLeft+1] = 0;
          person++;
          move-=demLeft;
        } 
        else if (demLeft > demRight) {
          visited[currentGate+demRight-1] = j+1;
          person--;
          move+=demRight;
          backtrack();
          visited[currentGate+demRight-1] = 0;
          person++;
          move-=demRight;
        }
        else {
          visited[currentGate-demLeft+1] = j+1;
          person--;
          move+=demLeft;
          backtrack();
          visited[currentGate-demLeft+1] = 0;
          person++;
          move-=demLeft;
          
          visited[currentGate+demRight-1] = j+1;
          person--;
          move+=demRight;
          backtrack();
          visited[currentGate+demRight-1] = 0;
          person++;
          move-=demRight;
        }
        
        visited2[j] = 0;
        move -= tot;
        for (int k = 0; k < N; k++) {
          if (visited[k] == j + 1) {
            visited[k] = 0;
          }
        }
      }
    }
  }
  
  public static void main(String[] args) throws FileNotFoundException {
    System.setIn(new FileInputStream("C:\\Users\\lehuyen130901\\eclipse-workspace\\BackTrack\\src\\input.txt"));
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    for (int t1 = 1; t1 <= t; t1++) {
      N = sc.nextInt();
      arr = new int[N];
      gate = new int[3];
      numOfPerson = new int[3];
      
      res = Integer.MAX_VALUE;
      for (int i = 0; i < 3; i++) {
        gate[i] = sc.nextInt() - 1;
        numOfPerson[i] = sc.nextInt();
      }
      
      move = 0;
      visited = new int[N];
      visited2 = new int[N];
      backtrack();
      
      System.out.println("Case #" + t1);
      System.out.println(res);
    }
    sc.close();
  }
}
Editor is loading...
Leave a Comment