bugs.pas

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

program bugs;

const ifn='bugs.dat';	{输入文件名}
      ofn='bugs.out';	{输出文件名}
      maxsize=1023;
      maxm=100;		{最大补丁数}
      maxn=20;		{最大bug数}

type datatype=array[0..maxsize] of longint;

var data:array[0..maxsize] of ^datatype;		{存储软件错误的状态的时间}
    time:array[1..maxm] of longint;		{补丁的应用时间}
    check:array[1..maxm,0..1] of longint;	       {补丁的应用条件}
    change:array[1..maxm,0..1] of longint;	{补丁的应用效果}
    exist:array[1..maxn] of boolean;		{是否有补丁可以修复错误}
    n,m,goal,mintime:longint;
    can:boolean;

procedure init_data;		                     {状态搜索的初始化}
var i,j,k:longint;
begin
  fillchar(check,sizeof(check),0);
  fillchar(change,sizeof(change),0);
  fillchar(exist,sizeof(exist),false);
  mintime:=-1;
  goal:=1;
  for i:=1 to n do goal:=goal*2;
  dec(goal);
  k:=(goal div (maxsize+1))+1;
  for i:=0 to k do begin
    new(data[i]);
    for j:=0 to maxsize do data[i]^[j]:=maxlongint;
  end;
  data[0]^[0]:=0;
end;

function get_state(a,b:longint):longint;		{寻找当前用时最少的未扩展状态}
var i,k,o,x,y:longint;
begin
  o:=-1;  k:=maxlongint;
  for i:=a to b do begin
    x:=i div (maxsize+1);
    y:=i mod (maxsize+1);
    if (data[x]^[y]>=0) and (data[x]^[y]<k) then
     begin k:=data[x]^[y]; o:=i; end;
  end;
  get_state:=o;
end;

function check_state(x,z:longint):boolean;	{检查补丁应用条件}
begin
  if (not(x) and check[z,0]=check[z,0]) and
     (x and check[z,1]=check[z,1])
     then check_state:=true
     else check_state:=false;
end;

function change_state(x,z:longint):longint;	{应用补丁，转变错误状态}
begin
  x:=not(not(x) or change[z,0]);
  x:=x or change[z,1];
  change_state:=x;
end;

procedure read_data;		       {读数据}
var f:text;
    i:longint;

 procedure make_check(x:longint);	{读入补丁的应用条件}
 var s:string;
     c:char;
     j,k:longint;
 begin
   s:='';
   read(f,c);
   for j:=1 to n do
    begin read(f,c); s:=c+s; end;
   k:=1;
   for j:=1 to n do begin
     if s[j]='+' then inc(check[x,0],k);
     if s[j]='-' then inc(check[x,1],k);
     k:=k*2;
   end;
 end;

 procedure make_change(x:longint);		{读入补丁的应用效果}
 var s:string;
     c:char;
     j,k:longint;
 begin
   s:='';
   read(f,c);
   for j:=1 to n do
    begin read(f,c); s:=c+s; end;
   k:=1;
   for j:=1 to n do begin
     if s[j]='+' then inc(change[x,0],k);
     if s[j]='-' then
      begin
        inc(change[x,1],k);
        exist[j]:=true;
      end;
     k:=k*2;
   end;
 end;

begin
  assign(f,ifn);
  reset(f);
    readln(f,n,m);
    init_data;
    for i:=1 to m do begin
      read(f,time[i]);
      make_check(i);
      make_change(i);
      readln(f);
    end;
  close(f);
  can:=true;
  for i:=1 to n do
   if not exist[i] then
    begin can:=false; exit; end;
end;

procedure search;	     {广度优先扩展搜索}
var min,max,open,closed,x,y,xx,yy,t,i:longint;
begin
  min:=0;  max:=0;
  repeat
    open:=get_state(min,max);
    if open=-1 then exit;
    if open=goal then continue;
    x:=open div (maxsize+1);
    y:=open mod (maxsize+1);
    t:=data[x]^[y];
    for i:=1 to m do
     if check_state(open,i) then
      begin
        closed:=change_state(open,i);
        xx:=closed div (maxsize+1);
        yy:=closed mod (maxsize+1);
        if t+time[i]<data[xx]^[yy] then
         begin
           data[xx]^[yy]:=t+time[i];
           if closed>max then max:=closed;
         end;
      end;
    data[x]^[y]:=-1;
    if open=min then
     repeat
       inc(min);
     until data[min div (maxsize+1)]^[min mod (maxsize+1)]>=0;
  until open=goal;
  mintime:=data[goal div (maxsize+1)]^[goal mod (maxsize+1)];
end;

procedure write_data;	{输出结果}
var f:text;
begin
  assign(f,ofn);
  rewrite(f);
    writeln(f,mintime);
  close(f);
end;

begin		{主程序}
  read_data;
  if can then search;
  write_data;
end.