#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <vector>
using namespace std;
int dis (int a, int n)
{
return abs (a * 2 + 1 - n) + 1;
}
int floor (int x, int y, int n)
{
int a = dis (x, n);
int b = dis (y, n);
return max (a, b);
}
int init_floor_sum[] = {0, 1};
vector<int> floor_sum(init_floor_sum, init_floor_sum + 2);
int convert (int x, int y, int n)
{
for (size_t i = floor_sum.size(); i <= n; ++i)
floor_sum.push_back(i * i);
int f = floor (x, y, n);
int sum = floor_sum[f];
int dx = x - (n - f) / 2;
int dy = y - (n - f) / 2;
int f1 = f - 1;
int d; // d is zero-order in the floor
if (f1 == 0)
d = 0;
else if ((dx == 0) && (dy > 0)) // left
d = 4 * f1 - dy;
else if ((dx > 0) && (dy == f1)) // bottom
d = 3 * f1 - dx;
else if ((dx == f1) && (dy < f1)) // right
d = f1 + dy;
else // top
d = dx;
return floor_sum[n] - (sum - d);
}
void convert (int n, int p, int& x, int& y)
{
for (size_t i = floor_sum.size(); i <= n; ++i)
floor_sum.push_back(i * i);
int r = floor_sum[n] - p;
int f = n % 2;
for (; floor_sum[f] < r; f += 2)
;
int f1 = f - 1;
int sum = floor_sum[f];
int d = sum - r;
int dx, dy;
if (f1 == 0)
{
dx = 0;
dy = 0;
}
else if (d >= 3 * f1)
{
dx = 0;
dy = 4 * f1 - d;
}
else if (d >= 2 * f1)
{
dy = f1;
dx = 3 * f1 - d;
}
else if (d >= f1)
{
dx = f1;
dy = d - f1;
}
else
{
dy = 0;
dx = d;
}
x = dx + (n - f) / 2;
y = dy + (n - f) / 2;
}
void test (int x, int y, int n, int d)
{
int t = convert (x, y, n);
if (t != d)
printf ("(%d, %d) of %d\t\tneed: %d\t\tget:%d\n",
x, y, n, d, t);
int a, b;
convert (n, d, a, b);
if ((x != a) || (y != b))
printf ("%d floors at %d, need (%d, %d)\t\tget:(%d, %d)\n",
n, d, x, y, a, b);
}
int main()
{
test (0, 0, 1, 0);
test (0, 0, 2, 0);
test (1, 0, 2, 1);
test (1, 1, 2, 2);
test (0, 1, 2, 3);
test (0, 0, 3, 0);
test (1, 0, 3, 1);
test (2, 0, 3, 2);
test (2, 1, 3, 3);
test (2, 2, 3, 4);
test (1, 2, 3, 5);
test (0, 2, 3, 6);
test (0, 1, 3, 7);
test (1, 1, 3, 8);
test (0, 0, 4, 0);
test (3, 0, 4, 3);
test (3, 1, 4, 4);
test (3, 2, 4, 5);
test (3, 3, 4, 6);
test (1, 3, 4, 8);
test (0, 3, 4, 9);
test (0, 1, 4, 11);
test (1, 1, 4, 12);
test (2, 1, 4, 13);
test (2, 2, 4, 14);
test (1, 2, 4, 15);
char buf[1024];
gets (buf);
vector<int> line;
for (const char* p = buf; *p;)
{
while (*p && !isdigit(*p))
++p;
if (!*p)
break;
line.push_back(atoi(p));
while (isdigit(*p))
++p;
}
int n = line.size();
vector<int> queue(line);
queue.resize(n * n);
for (int y = 1; y < n; ++y)
for (int x = 0; x < n; ++x)
scanf ("%d", &queue[convert(x, y, n)]);
vector<vector<int> > array(n, vector<int>(n));
printf ("%dx%d, result is:\n", n, n);
for (int i = 0; i < queue.size(); ++i)
{
printf ("%8d", queue[i]);
int x, y;
convert (n, i, x, y);
array[y][x] = queue[i];
}
printf ("\n");
printf ("the 2d-array is:\n");
for (int y = 0; y < n; ++y)
{
for (int x = 0; x < n; ++x)
printf ("%8d", array[y][x]);
printf ("\n");
}
printf ("\n");
getchar();
}
|