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 5after 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:
#include#include #include #include #include #include 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;}