首页 > 代码库 > InPlace Transition of a matrix

InPlace Transition of a matrix

2024-07-01 21:57:54   228人阅读

Problem illustration:

given a n*n matrix, print its transition, for example , 90 degree clockwise,using only constant additional space

analysis:

using O(n^2) space is common,but for constant assistant space, we need to adopt constant space

solution:

use in place replacement, 

take

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

for example

the expected output is

21 16 11 6 1
22 17 12 7 2
23 18 13 8 3
24 19 14 9 4
25 20 15 10 5

after transition,value (0,0) is expected to be transferred to pos(0,4),while(0,4)→(4,4),(4,4) to (4,0),(4,0)to (0,0),which is the same with our 

so this four elements are called a cycle(for more clear explanation, please refer to situ permutation)

 

two keypoints:

1.with the same example,since we use (0,0) to cover (4,0),then the original value at (4,0) must be stored before coverage or the whole cycle will be initialized

to the cycle header

2.edge condition handling

 

source code for above example:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<string>
#include<algorithm>
 
using namespace std;
const int maxn = 100;
int matrix1[maxn][maxn];
int matrix2[maxn][maxn];
void trans(int h,int w)
{
    for(int i = 0; i < h; ++i)
    {
        for(int j = 0; j < w; ++j)
        {
            //要旋转的元素是m1[i+1][j+1]，转过去的位置是m2[j][n-i]
            matrix2[j][w-i-1] = matrix1[i][j];
        }
    }
    return;
}
inline void getPos(int orix,int oriy,int *newx,int *newy){
    (*newx) = oriy;
    (*newy) = 4 - orix;
//  return 0;
}
void inPlaceTrans(int i,int j){ //(i,j)为转换的起点
    int total = 25;
    int cnt = 0;
    int x = -1,y = -1;
    int orix = i,oriy = j;
    bool visit[5][5];
    memset(visit,0,sizeof(visit));
    visit[i][j] = 1;
    int tmp1,tmp2;
    while(cnt < total){    //我去，移反了，所有的值都initialize成圈头值了
        //a new cycle
        orix = i; oriy = j;
        getPos(i,j,&x,&y); //(i,j)的目标地址
        visit[i][j] = true;//这个位置的元素已经被移到目标地址
        tmp1 = matrix1[i][j];
        while(!(x == orix && y == oriy)){  //这个圈没有到头
            tmp2 = matrix1[x][y];
            matrix1[x][y] = tmp1;
            ++cnt;  //移过去了一个元素
            i = x;
            j = y;
            visit[i][j] = true;
            tmp1 = tmp2;
            getPos(i,j,&x,&y);
        }
        matrix1[x][y] = tmp1;
        bool get = false;
        for(int u = 0; u < 5; ++u){
            for(int v = 0; v < 5; ++v){
                if(visit[u][v] == 0){   //这个元素还没有被移到目标地址
                    i = u;
                    j = v;
                    get = true;
                    break;
                }
            }
            if(get)
                break;
        }
        if(!get){   //所有元素都被移到目标地址
            break;
        }
    }
}
int main()
{
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    cout << "helloworld\n";
    for(int i = 0; i < 5; ++i)
    {
        for(int j = 0; j < 5; ++j)
        {
            scanf("%d",matrix1[i]+j);
        }
    }
    inPlaceTrans(0,0);
    for(int i = 0; i < 5; ++i)
    {
        for(int j = 0; j < 5; ++j)
        {
            printf("%d   ",matrix1[i][j]);
        }
        cout << endl;
    }
    cout << "hello world\n";
    return 0;
}

　　

 

 

 

 


联系
我们