UVAlive 5867 Finding Feasible Paths 题解

UVAlive 5867 Finding Feasible Paths 题解

题目

Tri_integral Summer Training 4

题意：

一个程序，按照当前的参数执行的顺序也不一样。对于所有可能的参数，检测题目给出的执行顺序是否可能。

题解：

模拟……有2种infeasible的情况：

1、没有数据能满足执行顺序（前后矛盾）。

2、没有正确返回，比如返回后应该执行11的，却跑到21去了，反过来也一样。

//Time:46ms
//Memory:0KB
//Length:2184B
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN (1<<17)
int pr[MAXN],ptop;
bool check(int a,int b,int &v,int &h)
{for(++h;;++h)switch(pr[h]){case 3:if(a>2)return false;v=b+1;break;case 4:if(a<=2)return false;break;case 6:if(a<=b)return false;++v;break;case 7:if(a>b)return false;break;case 8:--v;break;case 10:if(a>=b+1)return false;if(!check(a-1,b,v,h)) return false;if(pr[h+1]!=11)    return false;break;case 11:return false;if(!check(a-2,v,v,h)) return false;if(pr[h+1]!=14)    return false;break;case 12:if(a<b+1)return false;break;case 13:if(!check(a-3,v,v,h)) return false;if(pr[h+1]!=14)    return false;break;case 15:return true;}return false;
}
int main()
{//freopen("/home/moor/Code/input","r",stdin);int ncase,tmp;bool flag;scanf("%d",&ncase);while(ncase--){flag=0;for(int i=0;i<5;++i)scanf("%d",&pr[i]);for(ptop=0;;++ptop){scanf("%d",&pr[ptop]);if(pr[ptop]==21)break;}for(int x=0;x<=20&&!flag;++x)for(int y=0;y<=100&&!flag;++y){int th=-1;tmp=0;flag=check(x,y,tmp,th);if(pr[th+1]!=21)flag=0;}printf("%sn",flag?"feasible":"infeasible");}return 0;
}