From b66bca1e31050058cb9fd9124b635408b3453144 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Thu, 9 Dec 2021 08:50:24 +0100 Subject: [PATCH] part two --- 09b.c | 89 ++++++++++++++++++++++++++++++----------------------------- 1 file changed, 46 insertions(+), 43 deletions(-) diff --git a/09b.c b/09b.c index a332dd4..3db03bf 100644 --- a/09b.c +++ b/09b.c @@ -2,69 +2,62 @@ #include #include #include -#include #include struct point { int x; int y; }; struct entry { struct point key; UT_hash_handle hh; }; -#define push(x, y) {\ - if ((x) >= 1 && (y) >= 1 && (x) <= maxx+1 && (y) <= maxy+1)\ - stack[sp++] = (struct point){x, y};\ - } +bool havevisited(struct entry **visited, int x, int y) +{ + struct entry *e = NULL; + struct point p; + memset(&p, 0, sizeof(p)); + p.x = x; + p.y = y; + HASH_FIND(hh, *visited, &p, sizeof(struct point), e); + return e; +} -int basin(int grid[102][102], int maxx, int maxy, int x, int y) +void addvisited(struct entry **visited, struct point p) +{ + struct entry *e = calloc(1, sizeof(struct entry)); + e->key = p; + HASH_ADD(hh, *visited, key, sizeof(struct point), e); +} + +int basin(struct entry **visited, int grid[102][102], int x, int y) { - printf("calculate basin for: %d,%d -- ", x, y); struct point stack[1000]; memset(stack, 0, sizeof stack); - struct entry *visited = NULL; int sp = 0; int size = 0; stack[sp++] = (struct point){.x=x, .y=y}; struct point p; - struct entry *e; memset(&p, 0, sizeof p); while(--sp >= 0) { p = stack[sp]; - HASH_FIND(hh, visited, &p, sizeof(struct point), e); - if (e) + if (havevisited(visited, p.x, p.y)) continue; - - e = calloc(1, sizeof(struct entry)); - e->key = p; - HASH_ADD(hh, visited, key, sizeof(struct point), e); + addvisited(visited, p); if (grid[p.y][p.x] == 9) continue; size++; - push(p.x+1, p.y); - push(p.x-1, p.y); - push(p.x, p.y+1); - push(p.x, p.y-1); + if (!havevisited(visited, p.x+1, p.y)) + stack[sp++] = (struct point){.x=p.x+1, .y=p.y}; + if (!havevisited(visited, p.x-1, p.y)) + stack[sp++] = (struct point){.x=p.x-1, .y=p.y}; + if (!havevisited(visited, p.x, p.y+1)) + stack[sp++] = (struct point){.x=p.x, .y=p.y+1}; + if (!havevisited(visited, p.x, p.y-1)) + stack[sp++] = (struct point){.x=p.x, .y=p.y-1}; } - printf(" %d\n", size); return size; } -void insert(int tl[3], int s) -{ - if (s > tl[0] && s <= tl[1]) - tl[0] = s; - if (s > tl[1] && s <= tl[2]) { - tl[0] = tl[1]; - tl[1] = s; - } - if (s > tl[2]) { - tl[0] = tl[1]; - tl[1] = tl[2]; - tl[2] = s; - } -} - int main() { int grid[102][102]; @@ -85,13 +78,23 @@ int main() } int tl[3] = {0}; - for (int cy = 1; cy= tl[0]) { + tl[2] = tl[1]; + tl[1] = tl[0]; + tl[0] = s; + } else if (s >= tl[1]) { + tl[2] = tl[1]; + tl[1] = s; + } else if (s > tl[2]) { + tl[2] = s; + } + } + } + } printf("%d\n", tl[0]*tl[1]*tl[2]); } -- 2.20.1