矩阵遍历，求算法解决思路

矩阵遍历，求算法
本帖最后由 jiaoyun007 于 2013-04-09 14:49:00 编辑 一个M*N的矩阵，希望给定一个算法，由四周向中心螺旋式遍历，比如如下矩阵（两边的大括号略去）：

引用

 2  31  3  37 23
15 22 33 76 10
61 8  50 21 34
30 98 66 56 5

，由四周向中心遍历的顺序就是 2 -> 15 -> 61 -> 30 -> 98 -> 66 -> 56 -> 5 -> 34 -> 10 -> 23 -> 37 -> 3 -> 31 -> 22 -> 8 -> 50 -> 21 -> 76 -> 33 -> 22

求给出相应算法，谢谢了！
[解决办法]

#include <iostream>
#include <string>
#include "person.pb.h"

using namespace std;
using namespace tutorial;
int d[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};//4个方向， 下右上左
int n = 4, m = 5;
char b[4][5] = {0};

int ok(int x, int y)
{
    if(x < 0 
[解决办法]
 y < 0 
[解决办法]
 x >= n 
[解决办法]
 y >= m 
[解决办法]
 b[x][y])
        return 0;

    return 1;
}

void traverse(int matrix[4][5], int x, int y, int dir)
{
    b[x][y] = 1;
    printf("%d ", matrix[x][y]);
    for(int i = 0; i < 4; i++)
    {   
        int newdir = (dir + i) % 4;
        int newx = x + d[newdir][0];
        int newy = y + d[newdir][1];
        if(ok(newx, newy))
            traverse(matrix, newx, newy, newdir);
    }   
}

int main()
{
    int matrix[4][5]={2,31,3,37,23,
                    15,22,33,76,10,
                    61,8, 50,21,34,
                    30,98,66,56,5};

    traverse(matrix, 0, 0, 0); 

    return 0;
}

//output 
//2 15 61 30 98 66 56 5 34 10 23 37 3 31 22 8 50 21 76 33

------解决方案--------------------

我的算法，定义一个和矩阵相同维数的bool数组用来计算是否已遍历过该位置，然后定义一个方向变量，0向下，1向右，2向上，3向左，然后根据方向处理两个索引的自增或自减，同时处理一下临界情况就可以了，算法很朴素，不过结果是正确的，代码示例如下：

#define M 4
#define N 4
int main()
{
 
    int n[M][N] = {
        4  ,6  ,7  ,8,
        4  ,2  ,3  ,1,
        12 ,43 ,54 ,9,
        56 ,7  ,90 ,10};
    bool b[M][N] = {0};     // 是否访问的标记数组，初始化为0
    int i = 0;      // 行索引
    int j = 0;      // 列索引
    // 输出第一个
    cout<<n[i][j] << " ";
    b[i][j] = 1;   // 每输出一个做个标记
    int nFlag = 0; // 表示前进方向 0:向下；1:向右，2:向上；3:向左
    for (int k = 1; k != M*N ;++k)
    {
        switch (nFlag)
        {
        case 0:
            {
                i++;
                if (i != M && !b[i][j] )
                {
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
                else
                {
                    nFlag = ++nFlag%4;
                    i--;    // i需要回退
                    j++;    // j需要做和nFlag==1同样的处理，因为将要进行向右遍历，其他方向的处理类似
                    // 这里需要显示一下，否则会有遗漏点
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
            }
        break;
        case 1:
            { 
 
                j++;
                if (j != N && !b[i][j] )
                {
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
                else
                {
                    nFlag = ++nFlag%4;
                    j--;
                    i--;
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }

            }
        break;
        case 2:
            {
                i--;
                if (i != -1 && !b[i][j] )
                {
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
                else
                {
                    nFlag = ++nFlag%4;
                    i++;
                    j--;
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
            } 
 
        break;
        case 3:
            {
                j--;
                if (j != -1 && !b[i][j] )
                {
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
                else
                {
                    nFlag = ++nFlag%4;
                    j++;
                    i++;
                    cout<<n[i][j] << " ";
                    b[i][j] = 1;
                }
            }
        break;
        }
    }

    return 0;
}

[解决办法]
仅供参考

#include <stdio.h>
#define MAXN 100
int m[MAXN+2][MAXN+2];
char d;
int x,y,k,n,w;
char str[10];
void main() {
    while (1) {
        printf("Input n(1..%d):",MAXN);
        fflush(stdout);
        rewind(stdin);
        if (1==scanf("%d",&n)) {
            if (1<=n && n<=MAXN) break;
        }
    }
    y=0  ;for (x=0;x<=n+1;x++) m[y][x]=1;
    y=n+1;for (x=0;x<=n+1;x++) m[y][x]=1;
    x=0  ;for (y=0;y<=n+1;y++) m[y][x]=1;
    x=n+1;for (y=0;y<=n+1;y++) m[y][x]=1;
    for (y=1;y<=n;y++) {
        for (x=1;x<=n;x++) {
            m[y][x]=0;
        }
    }
    x=1;
    y=1;
    k=0;
    d='D'; 
 
    while (1) {
        k++;
        if (k>n*n) break;
        m[y][x]=k;
        switch (d) {
            case 'D':
                if (0==m[y+1][x])  y++;
                else              {x++;d='R';}
            break;
            case 'R':
                if (0==m[y][x+1])  x++;
                else              {y--;d='U';}
            break;
            case 'U':
                if (0==m[y-1][x])  y--;
                else              {x--;d='L';}
            break;
            case 'L':
                if (0==m[y][x-1])  x--;
                else              {y++;d='D';}
            break;
        }
    }
    w=sprintf(str,"%d",n*n);
    for (y=1;y<=n;y++) {
        for (x=1;x<=n;x++) {
            printf(" %0*d",w,m[y][x]);
        }
        printf("\n");
    }
}

查看更多 下一篇