矩阵(由内向外)"/>
MxN螺旋矩阵(由内向外)
问题描述
按顺时针方向构建一个m * n的螺旋矩阵（或按顺时针方向螺旋访问一个m * n的矩阵）：在不构造螺旋矩阵的情况下，给定坐标i、j值求其对应的值f(i, j)。如对6 * 6矩阵， f(2, 0) =19 f(2, 1) = 6。
方案一
问题有两个：
1. 编程实现输出这个矩阵问题,我是采用模拟进行构造的，可以看到从1开始的方向变化始终是 right->down->left->up，所持续走的长度为1->1->2->2->3->3->...，发现了这个规律不难写出代码了！注意下面我把1的位置设置 在((n-1)/2, (n-1)/2)的位置。
void Simulate(int n) {int x, y;x = y = (n - 1) / 2; //1的位置data[x][y] = 1;int len = 1;int count = 0;int num = 2;DIRECTION dir = RIGHT;while(num <= n * n) {for(int i = 0; i < len; i++){switch(dir){case LEFT:--y; break;case RIGHT:++y; break;case UP:--x; break;case DOWN:++x; break;default: break;}data[x][y] = num++;}count++;if(count == 2) {count = 0;len++; }dir = (DIRECTION)((dir+1)%4);}
}代码如下:
//以(1,1)所在位置作为原点,向右作为x正半轴，向下作为y正半轴
int GetValue(int x, int y)
{int m = max(abs(x), abs(y));int rightBottom = m*m*4-2*m+1;int value = 0;if(x == -m){value = rightBottom +2*m+m-y;}else if(y == m){value = rightBottom+m-x;}else if(y == -m){value = rightBottom+4*m+x+m;}else if(x == m){value = rightBottom-(m-y);}return value;
}完整代码如下：
#include <iostream>
#include <cstdlib>
#include <algorithm>using namespace std;const int N = 100;int data[N + 1][N + 1];enum DIRECTION
{RIGHT, DOWN , LEFT, UP
};//模拟整个过程
void Simulate(int n)
{int x, y;x = y = (n-1)/2; //1的位置data[x][y] = 1;int len = 1;int count = 0;int num = 2;DIRECTION dir = RIGHT;while(num <= n*n){for(int i = 0; i < len; i++){switch(dir){case LEFT:--y; break;case RIGHT:++y; break;case UP:--x; break;case DOWN:++x; break;default: break;}data[x][y] = num++;}count++;if(count == 2){count = 0;len++; }dir =(DIRECTION)((dir + 1)%4);}
}//打印螺旋矩阵
void Output(int n){int i, j;for(i = 0; i < n; i++){cout << data[i][0];for(j = 1; j < n; j++)cout << "\t" << data[i][j];cout << endl;}
}//以(1,1)所在位置作为原点,向右作为x正半轴，向下作为y正半轴
int GetValue(int x, int y){int m = max(abs(x), abs(y));int rightBottom = m*m*4-2*m+1;int value = 0;if(x == -m){value = rightBottom+2*m+m-y;}else if(y == m){value = rightBottom+m-x;}else if(y == -m){value = rightBottom+4*m+x+m;}else if(x == m){value = rightBottom-(m-y);}return value;
}void TestPos(int n){int i, j;for(i = 0; i < n; i++){cout << GetValue(0-(n-1)/2,i-(n-1)/2);for(j = 1; j < n; j++)cout << "\t" << GetValue(j-(n-1)/2,i-(n-1)/2);cout << endl;}
}int main(){int n;while(cin >> n){if(n <= 0 || n > 100){cerr << "Size error!" << endl;break;}else{Simulate(n);Output(n);cout << endl;TestPos(n);}}return 0;
}方案二
MxN螺旋矩阵(由内向外)，而这一类螺旋矩阵，则是由内向外扩散。这两类矩阵可以通过下面的方法相互转换.由于是 n * n矩阵，对坐标（x，y）落在矩形的哪一条边上，可以直接使用x <= y进行判断，
原来的代码可以优化为：
int getv(int x, int y, int n) // 由外内向顺时针螺旋
{if (x <= y) {int k = min(x,n-1-y);return 4*k*(n-k)+1+(x+y-k*2);}int k = min(y, n-1-x)+1; return 4*k*(n-k)+1-(x+y-(k-1)*2);
}int getv_in(int x, int y, int n) // 由内向外顺时针螺旋
{if (n & 1) return n*n+1-getv(x,n-1-y,n);return n*n+1-getv(n-1-x,y,n);
}(i, i-1) ----------------------------------------- (i, t-i)
| |
| |
| |
(t-i, i-1) ----------------------------------------- (t-i, t-i)
对给定的坐标(x,y)，如果它落在某个这类矩形上，显然其所在的矩形起始点横坐标i满足：i = min{x, y+1, t-x, t-y}.第k个矩形内的所有点构成(2*k+2)*(2*k+3)矩阵，共有元素P(k)=(2*k+2)*(2*k+3)个,第k个矩形的起始点（i,i）对应的值为T(i)=P(k-1)+1=2*k*(2*k+1)+1=(t-2*i)*(t-2*i-1)+1.对某个矩形，设矩形上的点(x, y)到起始点(i,i)的距离d = x-i + y-i = x+y-2*i，设点(x, y)到下一起始点(i-1,i-1)的距离为dd，则 dd = d + 2.① 向右和向下都只是横坐标或纵坐标增加1，这两条边上的点满足f(x, y) = T(i) + d ② 向左和向下都只是横坐标或纵坐标减少1，这两条边上的点满足f(x, y) = T(i-1) –dd. 对矩阵的构建和另一种螺旋矩阵类似，
构建矩阵代码：
#include<cstdio>
const int N = 128;
int a[N][N];void set_1a(int n)
{const int nn = (n - 1) | 1;int x = nn / 2u, y = x, k = 0;for (int len = 1; len < nn; len += 2) {for (int j = 0; j < len; ++j) a[x][y++] = ++k;for (int j = 0; j < len; ++j) a[x++][y] = ++k;for (int j = 0; j <= len; ++j) a[x][y--] = ++k;for (int j = 0; j <= len; ++j) a[x--][y] = ++k;}for(int j = 0; j < nn; ++j) a[0][j] = ++k;if ((n & 1) == 0) {for (int j = 0; j < nn; ++j) a[j][nn] = ++k;for (int j = nn; j >= 0; --j) a[nn][j] = ++k; }
}void set_1b(int n)
{int len = 0, k = 0, x = (n - 1) / 2u, y = x;while (1) {++len;for (int j = 0; j < len; ++j) a[x][y++] = ++k;if (len == n) break;for (int j = 0; j < len; ++j) a[x++][y] = ++k;++len;for (int j = 0; j < len; ++j) a[x][y--] = ++k;if (len == n) break;for (int j = 0; j < len; ++j) a[x--][y] = ++k; }
}void set_2(int n)
{const int nn = (n - 1) | 1;int k = 0;for (int i = nn / 2u; i > 0; --i) {const int C = nn - i;for (int j = i; j < C; ++j) a[i][j] = ++k; for (int j = i; j < C; ++j) a[j][C] = ++k; for (int j = C; j >= i; --j) a[C][j] = ++k; for (int j = C; j >= i; --j) a[j][i - 1] = ++k;}for(int j = 0; j < nn; ++j) a[0][j] = ++k;if ((n & 1) == 0) {for (int j = 0; j < nn; ++j) a[j][nn] = ++k;for (int j = nn; j >= 0; --j) a[nn][j] = ++k; }
}void print(int n){for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j)printf("%3d ",a[i][j]);printf("\n");} printf("\n");
}int main(){for (int i = 3; i < 9; ++i) {set_1b(i);print(i);}
}对给定坐标求值的代码
int getv(int x, int y, int n){ //螺旋矩阵（由内向外扩散）int t = (n-1)|1;if (x <= y) {int k = min(x,t-y);return (t-2*k)*(t-2*k-1)+1+(x+y-2*k);}int k = min(y+1,t-x)-1;return (t-2*k)*(t-2*k-1)+1-(x+y-2*k);
}完整测试代码：
//螺旋矩阵（由内向外扩散），给定坐标直接求值
#include<iostream>
#include<algorithm>
using std::min;
using std::cout;int getv(int x, int y, int n) //螺旋矩阵（由内向外扩散）
{int t = (n-1)|1;if (x <= y) {int k = min(x, t-y);return (t-2*k)*(t-2*k-1)+1+(x+y-2*k);}int k = min(y + 1, t - x) - 1;return (t-2*k)*(t-2*k-1)+1-(x+y-2*k);
} int main(){const int M = 12;for (int k = 2; k < M; ++k) {for (int i = 0; i < k; ++i) {for (int j = 0; j < k; ++j) {cout.width(4);cout << getv(i, j, k) << " ";}cout << "\n"; }cout << "\n";}
}============================================================
更多推荐
MxN螺旋矩阵(由内向外)
发布评论