您身边的软件定制专家--9年开发经验为您护航

18678812288
0531-88887250

网站首页 关于我们 开发优势 产品展示
合作企业 新闻动态 联系我们 电话联系

POJ 3106Flip and Turn（模拟）

文章作者：济南软件开发 时间：2016年12月20日

Flip and Turn

Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 957
Accepted: 330

Description

Let us define a set of operations on a rectangular matrix of printable characters.

A matrix A with m rows (1-st index) and n columns (2-nd index) is given. The resulting matrix B is defined as follows.

Transposition by the main diagonal (operation identifier is ‘1’): Bj,i =Ai,jTransposition by the second diagonal (‘2’): Bn?j+1,m?i+1 = Ai,jHorizontal flip (‘H’): Bm?i+1,j = Ai,jVertical flip (‘V’): Bi,n?j+1 = Ai,jRotation by 90 (‘A’), 180 (‘B’), or 270 (‘C’) degrees clockwise; 90 degrees case: Bj,m?i+1 = Ai,jRotation by 90 (‘X’), 180 (‘Y’), or 270 (‘Z’) degrees counterclockwise; 90 degrees case: Bn?j+1,i =Ai,j

You are given a sequence of no more than 100 000 operations from the set. Apply the operations to the given matrix and output the resulting matrix.

Input

At the first line of the input file there are two integer numbers — m and n (0 < m, n≤ 300). Then there are m lines with n printable characters per line (we define a printable character as a symbol with ASCII code from 33 to 126 inclusive). There will be no additional symbols at these lines.

The next line contains the sequence operations to be performed, specified by their one-character identifiers. The operations should be performed from left to right.

Output

Two integer numbers, the number of rows and columns in the output matrix. Then the output matrix must follow, in the same format as the input one.

Sample Input

 

1

2

3

4

5

3 4

0000

a0b0

cdef

A1

Sample Output

 

1

2

3

4

3 4

cdef

a0b0

0000



题目大意：给你一个m*n的矩阵，通过顺时针旋转，逆时针旋转，水平翻转，垂直翻转，对角线旋转，反对角线旋转变换得到新矩阵。但是不能直接对原矩阵操作，时间复杂度为O(10^5*10^5)，会超时，但是如何保存变化的过程呢，我们不需要知道变化过程，只需要知道结果即可。由于旋转翻转都是中心对称的，可以采用一个2*2的小正方形记录变化情况，然后小矩阵变化得出最终结果之后再相应变化大矩阵。时间复杂度为O(10^5*5) 
题目地址：Flip and Turn 
AC代码：

 

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

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include

using namespace std;

char a[305][305];

char b[305][305];

char str[100005];

int m,n;

int tb[3][3];

 

void con1()

{

    int i,j;

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=m; j++)

        {

            b[i][j]=a[j][i];

        }

    }

 

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=m; j++)

            a[i][j]=b[i][j];

        a[i][j]='\0';

    }

    swap(n,m);

}

 

void con2()

{

    int i,j;

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

        {

            b[n-j+1][m-i+1]=a[i][j];

        }

    }

 

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=m; j++)

            a[i][j]=b[i][j];

        a[i][j]='\0';

    }

    swap(n,m);

}

 

void con3()

{

    int i,j;

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

        {

            b[m-i+1][j]=a[i][j];

        }

    }

 

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

            a[i][j]=b[i][j];

        a[i][j]='\0';

    }

}

 

void con4()

{

    int i,j;

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

        {

            b[i][n-j+1]=a[i][j];

        }

    }

 

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

            a[i][j]=b[i][j];

        a[i][j]='\0';

    }

}

 

void con5()

{

    int i,j;

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

        {

            b[j][m-i+1]=a[i][j];

        }

    }

 

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=m; j++)

            a[i][j]=b[i][j];

        a[i][j]='\0';

    }

    swap(m,n);

}

 

void con6()

{

    int i,j;

    for(i=1; i<=m; i++)

    {

        for(j=1; j<=n; j++)

        {

            b[n-j+1][i]=a[i][j];

        }

    }

 

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=m; j++)

            a[i][j]=b[i][j];

        a[i][j]='\0';

    }

    swap(m,n);

}

 

void debug()

{

    int i,j;

    for(i=1;i<=2;i++)

    {

        for(j=1;j<=2;j++)

            cout<<tb[i][j]<<" ";="" cout<<endl;="" }="" int="" main()="" {="" i,j;="" while(~scanf("%d%d",&m,&n))="" for(i="1;" i<="m;" i++)="" scanf("%s",a[i]+1);="" scanf("%s",str);="" tb[1][1]="1,tb[1][2]=2,tb[2][1]=3,tb[2][2]=4;" i<strlen(str);="" if(str[i]="='1')" swap(tb[1][2],tb[2][1]);="" else="" swap(tb[1][1],tb[2][2]);="" swap(tb[1][1],tb[2][1]);="" swap(tb[1][2],tb[2][2]);="" swap(tb[1][1],tb[1][2]);="" swap(tb[2][1],tb[2][2]);="">='A'&&str[i]<='C')

            {

                int s=str[i]-'A'+1;

                for(j=0;j<s;j++) {="" swap(tb[2][2],tb[1][2]);="" swap(tb[1][1],tb[1][2]);="" swap(tb[1][1],tb[2][1]);="" }="" else="" if(str[i]="">='X'&&str[i]<='Z')

            {

                int s=str[i]-'X'+1;

                for(j=0;j<s;j++) {="" swap(tb[1][1],tb[2][1]);="" swap(tb[1][1],tb[1][2]);="" swap(tb[2][2],tb[1][2]);="" }="" debug();="" 是中心对称，顺时针转，对称转，沿对角线折都是中心对称，所以1="" 4只能是对角="" if(tb[1][1]="=1&&tb[1][2]==2&&tb[2][1]==3&&tb[2][2]==4)" {}="" 1="" 2="" 3="" 4="" else="" con1();="" con4();="" con5();="" con2();="" {con2();="" con1();}="" con6();="" {con6();="" con2();}="" cout<<m<<"="" "<<n<<endl;="" for(i="1;" i<="m;" i++)="" cout<<br>

<br>

 

<br>                        </s;j++)></s;j++)></tb[i][j]<<"></algorith


想要了解更多详情欢迎来电咨询18678812288
登陆网址:www.jnydkj.cn。
联系人:王经理。