#include<iostream.h>

#define W 10
#define R 20

int m,n; //m個進程,n個資源
int Available[R];  //系統可用資源數
int Max[W][R];  //M個進程對N類資源最大資源需求量
int Allocation[W][R]; //M個進程已經得到N類資源的資源量
int Need[W][R];   //M個進程還需要N類資源的資源量
int Request[W][R];//每一個進程請求的各種資源
int Finish[W]; 
int p[W];  //存放安全序列

void Input(); //用戶輸入題目要求的資源數目
int IsSafe(); //安全性檢查 
int IsOut();  //判斷是否滿足進程的請求
/////////////////////////////////////////////////////////////////////////////////////////////////////
int main()             //銀行家算法
{
 Input();
 IsSafe();
 IsOut();
 return 0;

}
/////////////////////////////////////////////////////////////////////////////////
void Input() //用戶輸入題目要求的資源數目
{
int i,j;
 cout<<"輸入進程的數目:\n";
 cin>>m;
 cout<<"輸入資源的種類:\n";
 cin>>n;
 cout<<"輸入每個進程最多所需的各資源數,按照"<<m<<"x"<<n<<"矩陣輸入\n";
 for(i=0;i<m;i++)
  for(j=0;j<n;j++)
   cin>>Max[i][j];
 cout<<"輸入每個進程已分配的各資源數,也按照"<<m<<"x"<<n<<"矩陣輸入\n";
 for(i=0;i<m;i++)
 {
    for(j=0;j<n;j++)
	{
      cin>>Allocation[i][j];
      Need[i][j]=Max[i][j]-Allocation[i][j];
      if(Need[i][j]<0)
	  {
         cout<<"你輸入的第"<<i+1<<"個進程所擁有的第"<<j+1<<"個資源數錯誤,請重新輸入:\n";
         j--;
         continue;
	  }
	}
 }
 cout<<"請輸入各個資源現有的數目:\n";
 for(i=0;i<n;i++)
  cin>>Available[i];
}

int IsSafe()  //安全性檢查 
{
 int i,j,l=0;
 int Work[R]; //可利用資源數組
 for(i=0;i<n;i++)
     Work[i]=Available[i];
 for(i=0;i<m;i++)
      Finish[i]=0;
 for(i=0;i<m;i++)
 {
      if(Finish[i]==1) 
		  continue;
       else
	   {
           for(j=0;j<n;j++)
		   {
               if(Need[i][j]>Work[j]) 
				   break;
		   }
           if(j==n) //資源符合所有進程的要求
		   { 
              Finish[i]=1;
              for(int k=0;k<n;k++)
                   Work[k]+=Allocation[i][k]; //把進程i的資源釋放
              p[l++]=i;   //安全序列
              i=-1;  //從0開始再一次遍歷查找
		   }
           else continue; //跳過當前的不符合的，查找下一個
	   }   
 }
    if(l==m)//m是從1開始的，l是從0開始的
	{
         cout<<"系統是安全的"<<'\n';
         cout<<"安全序列是:\n";
         for(i=0;i<l;i++)
			{
                cout<<p[i];
                if(i!=l-1) 
					cout<<"-->"; 
			}
         cout<<'\n';
         return 1;
	}
	else
		return 0;
}

int IsOut()  //判斷是否滿足進程的請求
{
 int i,j,mi;
 while(1)
 {
   cout<<"輸入要申請資源的進程號(注:第1個進程號為0,依次類推)\n";
   cin>>mi;
   cout<<"輸入進程所請求的各資源的數量\n";
   for(i=0;i<n;i++)
   cin>>Request[mi][i];//進程mi需要的各類資源
   for(i=0;i<n;i++)
   {
     if(Request[mi][i]>Need[mi][i])
	 {
       cout<<"你輸入的請求數超過進程的需求量!\n";
       return 0;
     }
     if(Request[mi][i]>Available[i])
	 {
       cout<<"你輸入的請求數超過系統有的資源數!\n";
       return 0;
	 }
   }
   for(i=0;i<n;i++)
   {
     Available[i]-=Request[mi][i];
     Allocation[mi][i]+=Request[mi][i];
     Need[mi][i]-=Request[mi][i];
   }
   if(IsSafe()) cout<<"同意分配請求!\n";
   else
   {
     cout<<"你的請求被拒絕!\n";
     for(i=0;i<n;i++) //不能分配，把資源回收回來
	 {
       Available[i]+=Request[mi][i];
       Allocation[mi][i]-=Request[mi][i];
       Need[mi][i]+=Request[mi][i];
     }
   }
   for(i=0;i<m;i++)
     Finish[i]=0;
   char YesOrNo;
   cout<<"你還想再次請求分配嗎?是請按y/Y,否按n/N,再確定\n";
   while(1)
   {
     cin>>YesOrNo;
     if(YesOrNo=='y'||YesOrNo=='Y'||YesOrNo=='n'||YesOrNo=='N') //判斷大小寫
		 break;
     else
     {
       cout<<"請按要求輸入!\n";
       continue;
     }

   }
   if(YesOrNo=='y'||YesOrNo=='Y') continue;
   else break;
 }

}