My solution for a table size of 1000 to 1000 is 4.07 MB of memory. What should I do?

You shouldn't use table 1000*1000. It could be solved using table 1000*2

int x[100],y[100],max[100];

I used: bool table[1000][1000];  which is 0,95367431640625 MB.
table[i][j] = 1, if the respective quarter can be crossed diagonally, and '0' otherwise.
I also used an array a[1001], in which to store the distance, and several auxiliary variables.
The total memory used is 1128 KB.