[ZOJ 1011] NTA (dfs搜索)

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1011

题目大意:在一棵树上,给你起始状态,问你能否到达终止状态。

给了树的前序遍历序。

直接dfs搜索。

 #include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <functional>
#include <cmath>
#include <numeric>
#include <ctime>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define PB push_back
#define MP make_pair
#define SZ size()
#define CL clear()
#define AA first
#define BB second
#define EPS 1e-8
#define ZERO(x) memset((x),0,sizeof(x))
const int INF = ~0U>>;
const double PI = acos(-1.0); int n,m,k;
char in[];
vector<PII> v[][];
int tree[];
char ch[]; bool isAccepted(int sig){
return sig>=n-m;
} bool dfs(int rt,int sig){
// printf("rt = %d sig = %d\n",rt,sig); int rtVal = tree[rt]; if( rtVal==- ){
return isAccepted(sig);
}
// printf("rtVal = %d\n",rtVal);
bool res = false;
for(int i=;i<v[sig][rtVal].SZ;i++){
res = dfs(rt<<,v[sig][rtVal][i].AA);
if(!res) continue;
res &= dfs(rt<<|,v[sig][rtVal][i].BB);
if( res ) break;
} return res;
} int main(){
int kase = ;
while( scanf("%d%d%d",&n,&m,&k)!=EOF ){
getchar();
for(int i=;i<;i++) for(int j=;j<;j++) v[i][j].CL;
if( n==&&m==&&k== ) break;
for(int i=;i<n;i++){
for(int j=;j<k;j++){
gets(in);
istringstream sss(in);
int a,b;
while( sss>> a >> b ){
v[i][j].PB(MP(a,b));
// printf("v[%d][%d].PB(%d,%d)\n",i,j,a,b);
}
}
}
// puts("*****");
if( kase!= ) puts("");
printf("NTA%d:\n",kase++);
int q;
while( true ){
memset(tree,-,sizeof(tree));
scanf("%d",&q);
if( q==- ) break;
for(int i=;i<=(<<(q+))-;i++){
scanf("%s",&ch);
if( strcmp(ch,"*")== ){
tree[i] = -;
} else {
tree[i] = ch[]-'a';
}
// printf("%d ",tree[i]);
}//puts(""); bool ok = dfs(,);
if(ok) puts("Valid");
else puts("Invalid");
} }
return ;
}
上一篇:adb remount 失败remount failed: Operation not permitted


下一篇:Neo4J 教程