Chinaunix首页 | 论坛 | 博客
  • 博客访问: 578236
  • 博文数量: 79
  • 博客积分: 2513
  • 博客等级: 少校
  • 技术积分: 806
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-04 18:46
文章分类

全部博文(79)

文章存档

2014年(1)

2010年(5)

2009年(8)

2008年(11)

2007年(41)

2006年(13)

我的朋友

分类: C/C++

2007-04-25 10:40:42

这个程序可以匹配“顺时针螺旋矩阵”中的坐标与数字对,也就是给出数字,可以直接得出坐标;给出坐标,可以直接计算出数字。所谓的顺时针螺旋矩阵,如下:

三阶:
1 2 3
8 9 4
7 6 5


四阶:
 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7

调用的接口是:
转换坐标到数字
int
convert (int x, int y, int n)
x: x 坐标值(水平),左边从 0 开始,右边最大为 n - 1
y: y 坐标值(竖直),顶端从 0 开始,下端最大为 n - 1
n: 矩阵的阶数,等同于矩阵的边长,也就是 n*n 的矩阵
返回值: n*n 的顺时针螺旋矩阵在 (x, y) 位置上的数字。数字从 1 开始

转换数字到坐标
void convert (int n, int p, int& x, int& y)
n: 矩阵的阶数
p: 要查找坐标的数字,从 1 开始,最大到 n*n
输出 x: p 在矩阵的 x 坐标值(水平),左边从 0 开始
输出 y: p 在矩阵的 y 坐标值(竖直),顶端从 0 开始

设定:
  1. n 表示矩阵的边长
  2. 坐标以左上角为原点,x 轴从左向右增长,y 轴自上而下增长
  3. 数字从 1 开始增长到 n*n
程序很久前写的:)

#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();
}


阅读(2984) | 评论(2) | 转发(0) |
0

上一篇:URL 中的百分号的麻烦

下一篇:新买三本书

给主人留下些什么吧!~~