![;)](./images/smilies/icon_wink.gif)
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
int x;
int y;
} COORD;
typedef struct
{
char ch;
int inputs_needed;
int (*func)();
} GATETYPE;
typedef struct
{
char inputs[2];
int ninputs;
COORD outputs[20];
int noutputs;
GATETYPE *gate;
} GATE;
int do_and(GATE *);
int do_or(GATE *);
int do_not(GATE *);
int do_input(GATE *);
int do_output(GATE *);
GATETYPE gatetypes[5] =
{
{ '&', 2, do_and },
{ '|', 2, do_or },
{ '!', 1, do_not },
{ 'i', 1, do_input },
{ 'o', 1, do_output }
};
#define G_AND (&gatetypes[0])
#define G_OR (&gatetypes[1])
#define G_NOT (&gatetypes[2])
#define G_INPUT (&gatetypes[3])
#define G_OUTPUT (&gatetypes[4])
GATE gates[100];
int ngates;
GATE *grid[10][10];
int parse_coord(char **str, COORD *coord)
{
char *p = *str;
while(*p == ' ')
p++;
if((!*p || !*(p+1)) || (*p == '.' && *(p+1) == '.'))
return 0;
coord->x = *p-'0';
coord->y = *(p+1)-'0';
*str = p+2;
return 1;
}
void run_it(void)
{
int x, y, i;
int nprocessed;
int val;
GATE *g, *g2;
do
{
nprocessed = 0;
for(x = 0;x < 10;++x)
for(y = 0;y < 10;++y)
{
g = grid[x][y];
if(g && g->gate != G_OUTPUT)
{
if(g->ninputs == g->gate->inputs_needed)
{
val = g->gate->func(g);
g->ninputs = 0;
nprocessed++;
for(i = 0;i < g->noutputs;++i)
{
g2 = grid[g->outputs[i].x][g->outputs[i].y];
g2->inputs[g2->ninputs++] = val;
}
}
}
}
} while(nprocessed);
}
int main(void)
{
char buf[4096], *p;
int ncircuits;
int x, y, ch;
int i;
int ntests;
GATE *g;
COORD c;
fgets(buf, sizeof(buf), stdin);
ncircuits = atoi(buf);
while(ncircuits--)
{
memset(grid, 0, sizeof(GATE *)*10*10);
memset(gates, 0, sizeof(GATE)*100);
ngates = 0;
for(;;)
{
fgets(buf, sizeof(buf), stdin);
if(*buf && buf[strlen(buf)-1] == '\n')
buf[strlen(buf)-1] = '\0';
if(!strcmp(buf, "end"))
break;
x = buf[0]-'0';
y = buf[1]-'0';
ch = buf[2];
for(i = 0;i < 5;++i)
if(gatetypes[i].ch == ch)
break;
if(i == 5)
continue;
gates[ngates].gate = &gatetypes[i];
grid[x][y] = &gates[ngates++];
g = grid[x][y];
p = buf+4;
while(parse_coord(&p, &c))
g->outputs[g->noutputs++] = c;
}
fgets(buf, sizeof(buf), stdin);
ntests = atoi(buf);
while(ntests--)
{
fgets(buf, sizeof(buf), stdin);
if(*buf && buf[strlen(buf)-1] == '\n')
buf[strlen(buf)-1] = '\0';
for(p = buf, i = 0;i < ngates;++i)
if(gates[i].gate == G_INPUT)
{
gates[i].inputs[gates[i].ninputs++] = *p-'0';
p++;
}
run_it();
for(i = 0;i < ngates;++i)
if(gates[i].gate == G_OUTPUT)
{
printf("%d", gates[i].inputs[0]);
gates[i].ninputs = 0;
}
printf("\n");
}
}
return 0;
}
int do_and(GATE *gate)
{
return gate->inputs[0] && gate->inputs[1];
}
int do_or(GATE *gate)
{
return gate->inputs[0] || gate->inputs[1];
}
int do_not(GATE *gate)
{
return !gate->inputs[0];
}
int do_input(GATE *gate)
{
return gate->inputs[0];
}
// do_output() shouldn't ever get called
int do_output(GATE *gate)
{
return 0;
}