雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

问题

1 按顺时针方向构建一个m * n的螺旋矩阵(或按顺时针方向螺旋访问一个m * n的矩阵):

2 在不构造螺旋矩阵的情况下,给定坐标ij值求其对应的值f(i, j)

比如对11 * 7矩阵, f(6, 0) = 27  f(6, 1) = 52 f(6, 3) = 76  f(6, 4) = 63

 

 

构建螺旋矩阵

对m * n 矩阵,最先访问最外层的m * n的矩形上的元素,接着再访问里面一层的 (m - 2) * (n - 2) 矩形上的元素…… 最后可能会剩下一些元素,组成一个点或一条线(见图1)。

对第i个矩形(i=0, 1, 2 …),4个顶点的坐标为:

(i, i) ----------------------------------------- (i, n–1-i)

|                                                    |

|                                                    |

|                                                    |

(m-1-i, i) ----------------------------------------- (m-1-i, n-1-i) 

要访问该矩形上的所有元素,只须用4个for循环,每个循环访问一个点和一边条边上的元素即可(见图1)。另外,要注意对最终可能剩下的1 * k 或 k * 1矩阵再做个特殊处理。

 

代码:

inline void act(int t) { printf("%3d ", t); }

 

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    for (int j = i; j < C; ++j) act(arr[i][j]);

    for (int j = i; j < R; ++j) act(arr[j][C]);

    for (int j = C; j > i; --j) act(arr[R][j]);

    for (int j = R; j > i; --j) act(arr[j][i]);

 }

 

 if (small & 1) {

    const int i = count;

    if (row <= col) for (int j = i; j < col - i; ++j) act(arr[i][j]);

    else for (int j = i; j < row - i; ++j) act(arr[j][i]);

}

 

如果只是构建螺旋矩阵的话,稍微修改可以实现4个for循环独立:

 

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    const int cc = C - i;

    const int rr = R - i;

    const int s = 2 * i * (row + col - 2 * i) + 1;

    for (int j = i, k = s; j < C; ++j) arr[i][j] = k++;

    for (int j = i, k = s + cc; j < R; ++j) arr[j][C] = k++;

    for (int j = C, k = s + cc + rr; j > i; --j) arr[R][j] = k++;

    for (int j = R, k = s + cc * 2 + rr; j > i; --j) arr[j][i] = k++;

 }

 

 if (small & 1) {

    const int i = count;

    int k = 2 * i * (row + col - 2 * i) + 1;

    if (row <= col) for (int j = i; j < col - i; ++j) arr[i][j] = k++;

    else for (int j = i; j < row - i; ++j) arr[j][i] = k++;

 }

 

关于s的初始值取 2 * i * (row + col - 2 * i) + 1请参考下一节。

 

由于C++的二维数组是通过一维数组实现的。二维数组的实现一般有下面三种:

静态分配足够大的数组;

动态分配一个长为m*n的一维数组;

动态分配m个长为n的一维数组,并将它们的指针存在一个长为m的一维数组。

二维数组的不同实现方法,对函数接口有很大影响。

 

 

 

 

给定坐标直接求值f(x, y)

 

如前面所述,对第i个矩形(i=0, 1, 2 …),4个顶点的坐标为:

(i, i) ----------------------------------------- (i, n–1-i)

|                                                    |

|                                                    |

|                                                    |

(m-1-i, i) ----------------------------------------- (m-1-i, n-1-i) 

对给定的坐标(x,y),如果它落在某个这类矩形上,显然其所在的矩形编号为:

k = min{x, y, m-1-x, n-1-y}

m*n矩阵删除访问第k个矩形前所访问的所有元素后,可得到(m-2*k)*(n-2*k)矩阵,因此已访问的元素个数为:m*n-(m-2*k)*(n-2*k)=2*k*(m+n-2*k),因而 (k,k)对应的值为:

T(k) = 2*k*(m+n-2*k)+ 1

 

对某个矩形,设点(x, y)到起始点(k,k)的距离d = x-k + y-k = x+y-2*k

① 向右和向下都只是横坐标或纵坐标增加1,这两条边上的点满足f(x, y) = T(k) + d

② 向左和向下都只是横坐标或纵坐标减少1,这两条边上的点满足f(x, y) = T(k+1) - d

 

如果给定坐标的点(x, y),不在任何矩形上,则它在一条线上,仍满足f(x, y) = T(k) + d

 

int getv(int row, int col, int max_row, int max_col) // row < max_row, col < max_col

{

 int level = min(min(row, max_row - 1 - row), min(col, max_col - 1 - col));

 int distance = row + col - level * 2;

 int start_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 if (row == level || col == max_col - 1 - level ||

(max_col < max_row && level * 2 + 1 == max_col))

   return start_value + distance;

 int next_value = start_value + (max_row + max_col - 4 * level - 2) * 2;

 return next_value - distance;

}

 

特别说明

上面的讨论都是基于m*n矩阵的,对于特例n*n矩阵,可以做更多的优化。比如构建螺旋矩阵,如果n为奇数,则矩阵可以拆分为几个矩形加上一个点。前面的条件判断可以优化为:

if (small & 1) act[count][count];

甚至可以调整4个for循环的遍历元素个数(前面代码,每个for循环遍历n-1-2*i个元素,可以调整为:n-2*i,n-1-2*i, n-1-2*i,n-2-2*i)从而达到省略if判断。

 

 

 

测试代码

代码1

 

//螺旋矩阵,给定坐标直接求值 by flyinghearts

//www.cnblogs.com/flyinghearts

#include<iostream>

#include<algorithm>

using std::min;

using std::cout;

 

/*

int getv2(int row, int col, int max_row, int max_col) // row < max_row, col < max_col

{

 int level = min(min(row, max_row - 1 - row), min(col, max_col - 1 - col));

 int distance = row + col - level * 2;

 int start_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 if (row == level || col == max_col - 1 - level) return start_value + distance;

 //++level; int next_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 int next_value = start_value + (max_row + max_col - 4 * level - 2) * 2;

 if (next_value > max_col * max_row) return start_value + distance;

 return next_value - distance;

}

*/

 

int getv(int row, int col, int max_row, int max_col) // row < max_row, col < max_col

{

 int level = min(min(row, max_row - 1 - row), min(col, max_col - 1 - col));

 int distance = row + col - level * 2;

 int start_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 if (row == level || col == max_col - 1 - level || (max_col < max_row && level * 2 + 1 == max_col))

    return start_value + distance;

 //++level; int next_value = 2 * level * (max_row + max_col - 2 * level) + 1;

 int next_value = start_value + (max_row + max_col - 4 * level - 2) * 2;

 return next_value - distance;

}

 

 

int main()

{

 

 int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

 const int sz = sizeof(test) / sizeof(test[0]);

 for (int k = 0; k < sz; ++k) {

    int M = test[k][0];

    int N = test[k][1];  

    for (int i = 0; i < M; ++i) {

      for (int j = 0; j < N; ++j)

        cout.width(4), cout << getv(i, j, M, N) << " ";

     cout << "\n"; 

    }

    cout << "\n";

 }

}

 

 

 

 

代码2:

//螺旋矩阵 by flyinghearts#qq.com

//www.cnblogs.com/flyinghearts

#include<iostream>

 

 

int counter = 0;

 

inline void act(int& t)

{

 //std::cout.width(3), std::cout << t;

 t = ++::counter;

}

 

void act_arr(int *arr, int row, int col, int max_col) //col < max_col

{

 const int small = col < row ? col : row;

 const int count = small / 2;

 int *p = arr;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - 2 * i;

    const int R = row - 1 - 2 * i;

    for (int j = 0; j < C; ++j) act(*p++);

    for (int j = 0; j < R; ++j) act(*p), p += max_col;

    for (int j = 0; j < C; ++j) act(*p--);

    for (int j = 0; j < R; ++j) act(*p), p -= max_col;

    p += max_col + 1;

 }

 

 if (small & 1) {

    const int i = count;

    if (row <= col) for (int j = 0; j < col - 2 * i; ++j) act(*p++);

    else for (int j = 0; j < row - 2 * i; ++j) act(*p), p += max_col;

 }

}

 

 

void act_arr(int* arr[], int row, int col)

{

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    for (int j = i; j < C; ++j) act(arr[i][j]);

    for (int j = i; j < R; ++j) act(arr[j][C]);

    for (int j = C; j > i; --j) act(arr[R][j]);

    for (int j = R; j > i; --j) act(arr[j][i]);

 }

 

 if (small & 1) {

    const int i = count;

    if (row <= col) for (int j = i; j < col - i; ++j) act(arr[i][j]);

    else for (int j = i; j < row - i; ++j) act(arr[j][i]);

 }

}

 

void act_arr_2(int* arr[], int row, int col)

{

 const int small = col < row ? col : row;

 const int count = small / 2;

 for (int i = 0; i < count; ++i) {

    const int C = col - 1 - i;

    const int R = row - 1 - i;

    const int cc = C - i;

    const int rr = R - i;

    const int s = 2 * i * (row + col - 2 * i) + 1;

    for (int j = i, k = s; j < C; ++j) arr[i][j] = k++;

    for (int j = i, k = s + cc; j < R; ++j) arr[j][C] = k++;

    for (int j = C, k = s + cc + rr; j > i; --j) arr[R][j] = k++;

    for (int j = R, k = s + cc * 2 + rr; j > i; --j) arr[j][i] = k++;

 }

 

 if (small & 1) {

    const int i = count;

    int k = 2 * i * (row + col - 2 * i) + 1;

    if (row <= col) for (int j = i; j < col - i; ++j) arr[i][j] = k++;

    else for (int j = i; j < row - i; ++j) arr[j][i] = k++;

 }

}

 

void print_arr(int *arr, int row, int col, int max_col) //col < max_col

{

 for (int i = 0, *q = arr; i < row; ++i, q += max_col) {

    for (int *p = q; p < q + col; ++p)

     std::cout.width(4), std::cout << *p;

    std::cout << "\n";

 }

 std::cout << "\n";

}

 

void print_arr(int* a[], int row, int col) //col < max_col

{

 for (int i = 0; i < row; ++i) {

    for (int j = 0; j < col; ++j)

     std::cout.width(4), std::cout << a[i][j];

    std::cout << "\n"; 

 }  

 std::cout << "\n";

}

 

 

void test_1()

{

 const int M = 25;

 const int N = 25;

 int a[M][N];

 int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

 const int sz = sizeof(test) / sizeof(test[0]);

 std::cout << "Test 1:\n";

 for (int i = 0; i < sz; ++i) {

    int row = test[i][0];

    int col = test[i][1];

    if (row < 0 || row > M) row = 3;

    if (col < 0 || col > N) col = 3;

    ::counter = 0;

    act_arr(&a[0][0], row, col, N);

    print_arr(&a[0][0], row, col, N);

 }

}

 

void test_2()

{

 int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

 const int sz = sizeof(test) / sizeof(test[0]);

 std::cout << "Test 2:\n";

 for (int i = 0; i < sz; ++i) {

    int row = test[i][0]; 

    int col = test[i][1]; 

    int **arr = new int*[row];

    for (int i = 0; i < row; ++i) arr[i] = new int[col];

    ::counter = 0;

    act_arr(arr, row, col);

    print_arr(arr, row, col);

    for (int i = 0; i < row; ++i) delete[] arr[i];

    delete[] arr; 

 }

}

 

 

int main()

{

 test_1();

 test_2();

}

 

posted on 2010-12-23 23:09 flyinghearts 阅读(4849) 评论(3)  编辑 收藏 引用 所属分类: 算法

评论

# re: 螺旋矩阵 2010-12-24 10:10 _飞寒
寒~ 这不是我们学校的赛题么。。  回复  更多评论
  

# re: 螺旋矩阵 2010-12-25 11:20 flyinghearts
@_飞寒
那真凑巧  回复  更多评论
  

# re: 螺旋矩阵 2014-08-12 13:57 121e1212
int test[][2] = {{5, 5}, {5, 7}, {7, 5}, {4, 4}, {4, 6}, {6, 4}};

const int sz = sizeof(test) / sizeof(test[0]);

std::cout << "Test 2:\n";

for (int i = 0; i < sz; ++i) {

int row = test[i][0];

int col = test[i][1];

int **arr = new int*[row];

for (int i = 0; i < row; ++i) arr[i] = new int[col];
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理