http://acm.pku.edu.cn/JudgeOnline/problem?id=1048
Код:
#include <stdio.h>
#include <string.h>
char s[110][110];
int n,m,l[100],p[26];
char flag[110][110];
struct binarytree{
int type,value;
binarytree *left,*right;
int o1,o2,o3;
}node[1000];
bool check(int x,int y)
{
if (x<0||y<0) return 0;
if (x>=n||y>=l[x]) return 0;
if (flag[x][y]) return 0;
if
(s[x][y]!='-'&&s[x][y]!='|'&&s[x][y]!='o'&&s[x][y]!='+'&&s[x][y]!=')'&&s[x][y]!='>'&&!(s[x][y]>='A'&&s[x][y]<='Z')) return 0;
return 1;
}
void search(binarytree *nodeptr,int x,int y)
{
while(1){
flag[x][y]=true;
if (s[x][y]=='-'){
if (check(x,y-1)){
if (s[x][y-1]=='+'){
flag[x][y-1]=true;
if (check(x-1,y-1)&&s[x-1][y-1]=='|'){
x--,y--;
}else{
x++,y--;
}
continue;
}else if (s[x][y-1]=='-'){
y--;
continue;
}else if (s[x][y-1]=='o'||s[x][y-1]==')'||s[x][y-1]=='>'){
if (s[x][y-1]=='o'){
nodeptr->o3=1;
y-=2;
}else{
y--;
nodeptr->o3=0;
}
if (s[x][y]==')') nodeptr->type=1;
else nodeptr->type=0;
nodeptr->left=&node[m++];
nodeptr->right=&node[m++];
if (s[x+1][y-3]=='o'){
nodeptr->o1=1;
search(nodeptr->left,x+1,y-4);
}else{
nodeptr->o1=0;
search(nodeptr->left,x+1,y-3);
}
if (s[x-1][y-3]=='o'){
nodeptr->o2=1;
search(nodeptr->right,x-1,y-4);
}else{
nodeptr->o2=0;
search(nodeptr->right,x-1,y-3);
}
return;
}else if (s[x][y-1]>='A'&&s[x][y-1]<='Z'){
nodeptr->value=s[x][y-1]-'A';
nodeptr->left=0;
nodeptr->right=0;
return;
}
}else if (check(x,y+1)){
if (s[x][y+1]=='+'){
flag[x][y+1]=true;
if (check(x-1,y+1)&&s[x-1][y+1]=='|'){
x--,y++;
}else{
x++,y++;
}
}else if (s[x][y+1]=='-'){
y++;
continue;
}else if (s[x][y+1]>='A'&&s[x][y+1]<='Z'){
nodeptr->value=s[x][y+1]-'A';
nodeptr->left=0;
nodeptr->right=0;
return;
}
}
}else{
if (check(x+1,y)){
if (s[x+1][y]=='+'){
flag[x+1][y]=true;
if (check(x+1,y+1)&&s[x+1][y+1]=='-'){
x++,y++;
}else{
x++,y--;
}
continue;
}else if (s[x+1][y]=='|'){
x++;
continue;
}else if (s[x+1][y]>='A'&&s[x+1][y]<='Z'){
nodeptr->value=s[x+1][y]-'A';
nodeptr->left=0;
nodeptr->right=0;
return;
}
}else{
if (s[x-1][y]=='+'){
flag[x-1][y]=true;
if (check(x-1,y+1)&&s[x-1][y+1]=='-'){
x--,y++;
}else{
x--,y--;
}
continue;
}else if (s[x-1][y]=='|'){
x--;
continue;
}else if (s[x-1][y]>='A'&&s[x-1][y]<='Z'){
nodeptr->value=s[x-1][y]-'A';
nodeptr->left=0;
nodeptr->right=0;
return;
}
}
}
}
}
void find(int &x,int &y)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<l[i];j++)
if (s[i][j]=='?'){
x=i;
y=j;
return;
}
}
int evaluate(binarytree *root)
{
int t1,t2;
if (root->left==0) return p[root->value];
t1=evaluate(root->left)^root->o1;
t2=evaluate(root->right)^root->o2;
if (root->type==1) return (t1&t2)^root->o3;
else return (t1|t2)^root->o3;
}
int main()
{
int i,j,x,y;
char s2[27];
//freopen("logic.in","r",stdin);
while(gets(s[0])!=NULL)
{
n=1;
while(1)
{
for(i=0;i<100;i++) s[n][i]=0;
gets(s[n++]);
if (s[n-1][0]=='*') break;
}
for(i=0;i<n;i++) l[i]=strlen(s[i]);
for(i=0;i<n;i++)
for(j=0;j<l[i];j++)
flag[i][j]=false;
find(x,y);
flag[x][y]=true;
m=1;
if (s[x][y-1]=='-') search(&node[0],x,y-1);
if (s[x-1][y]=='|') search(&node[0],x-1,y);
if (s[x+1][y]=='|') search(&node[0],x+1,y);
while(1)
{
gets(s2);
if (s2[0]=='*') break;
for(i=0;i<26;i++) p[i]=s2[i]-'0';
printf("%d\n",evaluate(&node[0]));
}
for(i=0;i<100;i++) s[0][i]=0;
printf("\n");
}
return 0;
}