summaryrefslogtreecommitdiff
path: root/euler345.c
diff options
context:
space:
mode:
Diffstat (limited to 'euler345.c')
-rw-r--r--euler345.c67
1 files changed, 67 insertions, 0 deletions
diff --git a/euler345.c b/euler345.c
new file mode 100644
index 0000000..b598981
--- /dev/null
+++ b/euler345.c
@@ -0,0 +1,67 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int mxsum(int **m, int n, int d, int visited[])
+{
+ int ans;
+ int sel = -1;
+ if (d == n)
+ return 0;
+
+ /* select the biggest of the line first */
+ for (int i = 0; i < n; i++) {
+ if (!visited[i]) {
+ if (sel == -1)
+ sel = i;
+ else if (m[d][i] > m[d][sel])
+ sel = i;
+ }
+ }
+ visited[sel] = 1;
+ ans = m[d][sel] + mxsum(m, n, d+1, visited);
+ visited[sel] = 0;
+
+ for (int i = 0; i < n; i++) {
+ if (visited[i] || i == sel)
+ continue;
+ visited[i] = 1;
+ int t = m[d][i];
+ /* estimate the maximum value of remaining numbers */
+ int re = 0;
+ for (int j = d+1; j < n; j++) {
+ int linemax = 0;
+ for (int k = 0; k < n; k++) {
+ if (!visited[k] && m[j][k] > linemax)
+ linemax = m[j][k];
+ }
+ re += linemax;
+ }
+ if (t + re > ans) {
+ t += mxsum(m, n, d+1, visited);
+ }
+ visited[i] = 0;
+ if (t > ans)
+ ans = t;
+ }
+ return ans;
+}
+
+int main()
+{
+ int n;
+ int **m;
+ int visited[15];
+
+ scanf("%d", &n);
+ m = (int**)malloc(sizeof(int*) * n);
+ memset(visited, 0, sizeof(visited));
+ for (int i = 0; i < n; i++) {
+ m[i] = (int*)malloc(sizeof(int) * n);
+ for (int j = 0; j < n; j++) {
+ scanf("%d", &m[i][j]);
+ }
+ }
+
+ printf("%d\n", mxsum(m, n, 0, visited));
+}