全座標を回って計算して最大を求めるだけ。
java
1public class LargestProductInAGrid {
2 static final int SIZE = 20;
3 static final int[][] GRID = { //ファイル読み込みを省略, "04" 等と 0 をアタマにつけると 8 進数になってしまうので頭0は削除
4 { 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
5 {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
6 {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
7 {52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
8 {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
9 {24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
10 {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
11 {67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
12 {24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
13 {21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
14 {78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
15 {16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
16 {86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
17 {19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
18 { 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
19 {88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
20 { 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
21 {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
22 {20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
23 { 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48},
24 };
25 enum Dir {
26 RIGHTUP(1,-1), RIGHT(1,0), RIGHTDOWN(1,1), DOWN(0,1);
27 final int dx, dy;
28 Dir(int dx, int dy) {
29 this.dx = dx;
30 this.dy = dy;
31 }
32 }
33 static class PosValue {
34 int x=-1, y=-1;
35 Dir dir;
36 int value;
37 @Override
38 public String toString() {
39 return "x="+x+", y="+y+", dir="+dir+", value="+value;
40 }
41 }
42 public static void main(String[] args) {
43 PosValue max = new PosValue();
44 for(int x=0; x<SIZE; x++) {
45 for(int y=0; y<SIZE; y++) {
46 largest(x, y, max);
47 }
48 }
49 System.out.println(max);
50 }
51 static void largest(int x, int y, PosValue max) {
52 for(Dir dir : Dir.values()) {
53 int value = 1;
54 for(int i=0, xx=x, yy=y; i<4; i++, xx+=dir.dx, yy+=dir.dy) {
55 if(xx < 0 || xx >= SIZE || yy < 0 || yy >= SIZE) { //GRID 範囲外
56 value = 0;
57 break;
58 }
59 value *= GRID[yy][xx];
60 }
61 if(max.value < value) {
62 max.x = x;
63 max.y = y;
64 max.dir = dir;
65 max.value = value;
66 }
67 }
68 }
69}
c へ移植
c
1#include <stdio.h>
2#include <string.h>
3
4#define SIZE 20
5
6int GRID[SIZE][SIZE] = { //ファイル読み込みを省略, "04" 等と 0 をアタマにつけると 8 進数になってしまうので頭0は削除
7 { 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
8 {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
9 {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
10 {52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91},
11 {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
12 {24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50},
13 {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
14 {67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
15 {24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
16 {21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
17 {78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
18 {16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
19 {86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
20 {19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
21 { 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
22 {88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
23 { 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
24 {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16},
25 {20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
26 { 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48},
27};
28
29typedef struct {
30 char *name;
31 int dx, dy;
32} Dir;
33Dir dirs[] = {
34 {"RIGHTUP",1,-1},
35 {"RIGHT",1,0},
36 {"RIGHTDOWN",1,1},
37 {"DOWN",0,1}
38};
39
40typedef struct {
41 int x, y;
42 Dir *dir;
43 int value;
44} PosValue;
45
46void largest(int x, int y, PosValue *max) {
47 for(int j=0; j<sizeof(dirs)/sizeof(Dir); j++) {
48 Dir *dir = &dirs[j];
49 int value = 1;
50 for(int i=0, xx=x, yy=y; i<4; i++, xx+=dir->dx, yy+=dir->dy) {
51 if(xx < 0 || xx >= SIZE || yy < 0 || yy >= SIZE) { //GRID 範囲外
52 value = 0;
53 break;
54 }
55 value *= GRID[yy][xx];
56 }
57 if(max->value < value) {
58 max->x = x;
59 max->y = y;
60 max->dir = dir;
61 max->value = value;
62 }
63 }
64}
65
66int main(int argc, char *argv[]) {
67 PosValue max;
68 memset(&max, 0, sizeof(PosValue));
69 for(int x=0; x<SIZE; x++) {
70 for(int y=0; y<SIZE; y++) {
71 largest(x, y, &max);
72 }
73 }
74 printf("x=%d, y=%d, dir=%s, value=%d\n", max.x, max.y, max.dir->name, max.value);
75 return 0;
76}
実行結果
plain
1x=3, y=15, dir=RIGHTUP, value=70600674