import java.util.Arrays;

public class BanksTest {
  // 用于存儲預操作后的資源變化
  static int[] new_Avaliable = null;
  // 用于存儲預操作的完成度
  static boolean[] new_finish = null;
  // 用于保存最終的進程執行順序,初始化為非法進程-1
  static int right[] = { -1, -1, -1, -1, -1 };

  public static void main(String[] args) {
    // 最大需求量
    int[][] max = { { 7, 5, 3 }, { 3, 2, 2 }, { 9, 0, 2 }, { 2, 2, 2 }, { 4, 3, 3 } };
    // 當前系統可用資源量
    int[] avaliable = { 3, 3, 2 };
    // 每個進程運行還需資源量
    int[][] need = new int[5][3];
    // 每個進程已分配的資源量
    int[][] allocation = { { 0, 1, 0 }, { 2, 0, 0 }, { 3, 0, 2 }, { 2, 1, 1 }, { 0, 0, 2 } };
    // 用于第一深度預判的初始化
    boolean finish[] = { false, false, false, false, false };
    // 獲取每個進程運行時還需的資源量
    for (int i = 0; i < max.length; i++) {
      for (int j = 0; j < max[i].length; j++) {
        need[i][j] = max[i][j] - allocation [i][j];
      }
    }
    // 創建遞歸深度
    int deep = 0;
    // 調用回溯遞歸算法
    deepCheck(avaliable, allocation, need, finish, deep, right);
    int i = 0;
    // 查看最終的安全序列的值，看是否存在初始的非法進程，如果存在，則說明該案例不存在安全的進程執行順序
    for (; i < right.length; i++) {
      if (right[i] == -1) {
        break;
      }
    }
    if (i < right.length) {
      System.out.println("該案例不存在安全的進程執行順序");
      return;
    }
    // 打印安全的執行順序
    for (int j = 0; j < right.length; j++) {
      System.out.println(right[j]);

    }

  }

  // 完全遞歸回溯查找安全順序
  public static boolean deepCheck(int[] avaliable, int[][] allocation, int[][] need, boolean finish[], int deep,
      int right[]) {
    int j = 0;
    boolean flog = false;
    // 如果深度為進程的個數數說明已經查找到頭了,說明上一深度的進程是安全節點。因為上一深度的進程滿足了當前資源數大于或等于該進程運行所需的資源數，且為安全序列中最后一個節點。
    if (deep == need.length) {
      return true;
    }
    // 遍歷所有節點進程開始查找,直到找到安全校驗成功的的節點進程
    for (int i = 0; i < need.length; i++) {
      // 對于未被標記的進行校驗，已被標記的為已被列為安全節點所以無需再進行校驗
      if (!finish[i]) {
        // 判斷當前的節點進程的剩余的資源量,是否滿足運行所需的資源量
        for (j = 0; j < avaliable.length; j++) {
          // 不滿足
          if (need[i][j] > avaliable[j]) {
            break;
          }
        }
        // 不滿足則處理下一個節點進程
        if (j < avaliable.length) {
          continue;
        } else {
          // 滿足情況
          // 復制會被修改的前提條件，已便于當前進程校驗不成功時，可以恢復前提條件，開始下一個節點進程的校驗
          new_Avaliable = Arrays.copyOf(avaliable, avaliable.length);
          new_finish = Arrays.copyOf(finish, finish.length);
          // 假設當前節點進程是可以校驗成功的節點進程，修改該進程運行完畢后釋放之前分配的進程。
          for (j = 0; j < new_Avaliable.length; j++) {
            new_Avaliable[j] += allocation[i][j];
          }
          // 假設標記當前為校驗成功的安全節點進程，下一深度查找時會忽略此進程。
          new_finish[i] = true;
          // 增加深度
          deep++;
          // 以上假設為前提，進行下一深度的安全校驗判斷其他所剩余進程是否可以繼續運行，而不造成死鎖。
          flog = deepCheck(new_Avaliable, allocation, need, new_finish, deep, right);
          // 如果進行安全校驗后為真，說明當前進程是我們要找的進程
          if (flog) {
            // 保存到最終進程執行序列的數組中
            right[--deep] = i;
            break;
          }

        }

      }

    }
    // 安全校驗成功
    if (flog) {
      return true;
    } else {
      // 安全校驗失敗
      // 清楚之前的假設標記
      new_finish[right[--deep]] = false;
      return false;
    }

  }
}