A couple of questions about multidimensional arrays has occurred to my mind.
- memory set of multidimensional arrays
- abstract method of dealing indices corresponding to dimensions
The first one is simple. I got a little confused when I was doing something like this:
int dp[2][64][64];
int main() {
/*
* some procedures here
*/
memset(dp[1], 0, sizeof(dp[1]));
}
So you want to set dp[1][i][j], i=0,1,..,63, j = 0,1,..,63, to zeros. Does this really work? what is the size of dp[1]?? A multidimensional array are actually a One-dimensional array. More specifically, memories are allocated to a multidimensional array as if it were a one-dimensional array. So dp[1] represents the address of dp[1][0][0]. So the size is 16384byte(64*64*8byte). It makes sense.
But how's about when you want to reset dp[0][i][j], i=0,1,..,63, j=0,1,..,63, leaving dp[1][i][j] unchanged? Does memset(dp[0], 0, sizeof(dp[0])) work? It's confusing this time.
What is the size of dp[0]? 16384byte? or 32768byte? The former is correct. Which reminds me that I sometimes do this kind of thing:
int buf[8][16];
int main() {
cout << sizeof(buf) / sizeof(buf[0]) << endl; // 8
cout << sizeof(buf[0]) / sizeof(buf[0][0]) << endl; // 16
}
The second question is difficult to describe. So I've prepared a simple, original problem to get the essence.
You are given a 6-dimensional array A[8][8][8][8][8][8]. Each element of A has an integer. You are given an integer n, an integer between 0 and 5, inclusive, which is the index of a moving dimension, and six integers (d0, d1, d2, d3, d4, d5), all of whom are integers between 0 and 7, inclusive. Calculate the sum A[d0'][d1'][d2'][d3'][d4'][d5'], where di' = {0,1,2,...,7} if i =n, otherwise di. (Sorry this statement may be awkward. In that case, see the example below.)
Here's an example. n = 1, (d1, d2, d3, d4, d5, d6) = (0,1,2,3,4,5).
You are to calculate A[0][0][2][3][4][5] + A[0][1][2][3][4][5] + A[0][2][2][3][4][5] + A[0][3][2][3][4][5] + A[0][4][2][3][4][5] + A[0][5][2][3][4][5] + A[0][6][2][3][4][5].
I first wrote a source code like this:
int A[8][8][8][8][8][8];
void init() {
REP(d0, 8)REP(d1, 8)REP(d2, 8)REP(d3, 8)REP(d4, 8)REP(d5, 8)
A[d0][d1][d2][d3][d4][d5] = d0 + d1 + d2 + d3 + d4 + d5;
}
int main() {
int n;
int d0, d1, d2, d3, d4, d5;
init();
cin >> n;
cin >> d0 >> d1 >> d2 >> d3 >> d4 >> d5;
int ans = 0;
switch (n) {
case 0:
REP(i, 8) ans += A[i][d1][d2][d3][d4][d5];
break;
case 1:
REP(i, 8) ans += A[d0][i][d2][d3][d4][d5];
break;
case 2:
REP(i, 8) ans += A[d0][d1][i][d3][d4][d5];
break;
case 3:
REP(i, 8) ans += A[d0][d1][d2][i][d4][d5];
break;
case 4:
REP(i, 8) ans += A[d0][d1][d2][d3][i][d5];
break;
default:
REP(i, 8) ans += A[d0][d1][d2][d3][d4][i];
}
cout << ans << endl;
}
Talk about a terrible code. Once you notice that a address is linear, you can write this cool code -- a friend of mine taught this implementation --. In this case, the size of each dimension is 8, imagine the base 8 number system, which will help you understand the code.
int A[8][8][8][8][8][8];
void init() {
REP(d0, 8)REP(d1, 8)REP(d2, 8)REP(d3, 8)REP(d4, 8)REP(d5, 8)
A[d0][d1][d2][d3][d4][d5] = d0 + d1 + d2 + d3 + d4 + d5;
}
int main() {
int n;
int d[6];
init();
cin >> n;
REP(i, 6) cin >> d[i];
d[n] = 0;
int ans = 0;
int *p = (int *)A;
int base = 1, move = 0;
REP(i, 6) {
if (6-1-i == n)
move = base;
p += d[6-1-i] * base;
base *= 8;
}
REP(i, 8)
ans += *(p + move * i);
cout << ans << endl;
}
