USACO 1.2.2 Transformations（模拟）

分析 这是我第一次在ACM的题目中用OO的思想写的程序，看到标程，竟不谋而合，结构是类的。对正方形这个类分析，将会使问题变得简单，我觉得OO的分析和设计挺关键的，其实我一开始也没设计好，原先准备把7个bool函数当成类的成员方法，其实这个设计是不好的，

分析

       这是我第一次在ACM的题目中用OO的思想写的程序，看到标程，竟不谋而合，结构是类似的。对正方形这个类分析，将会使问题变得简单，我觉得OO的分析和设计挺关键的，其实我一开始也没设计好，原先准备把7个bool函数当成类的成员方法，其实这个设计是不好的，有点过了。其实应该是把旋转90度和轴对称这两个方法作为类的成员方法，这样main中调用就方便自如了。

       最后，我觉得搞ACM，不仅是把题目A掉，同时也应注意程序的结构设计，因为”程序是给人看的“。

2013/3/31

       关于顺时针旋转90度，怎么由原来的坐标得到转换后的坐标，可以用计算机图像学里二维变换的知识，将连续推广到离散的，如下图所示。

       为了与二维数组对应，我将坐标系顺时针旋转了90度，这样就与二维数组的下标情况对应了，假设n为4。

关于变换矩阵，先把参考点移到原点，再顺时针旋转90度，最后移回原来参考点。复合变换矩阵：

MATLAB程序如下：

clc;
clear all;
syms x y n;

P = [x y 1];
xF = (n - 1) / 2.0;   % center = (xF yF)
yF = xF;
% theta = -pi / 2.0;

Tt1 = [
    1 0 0;
    0 1 0;
    -xF -yF 1
    ];

% 精度有损失
% Tr = [
%     cos(theta) sin(theta) 0;
%     -sin(theta) cos(theta) 0;
%     0 0 1
%     ];

Tr = [
    0 -1 0;
    1 0 0;
    0 0 1
    ];

Tt2 = [
    1 0 0;
    0 1 0;
    xF yF 1
    ];

Pt = P * Tt1 * Tr * Tt2;

display(P);
display(Pt);

变换结果

P =
 
[ x, y, 1]
 
 
Pt =
 
[ y, n - x - 1, 1]

源程序

// #define ONLINE_JUDGE
#define MY_DEBUG
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cassert>
using namespace std;

class Square {
private:
	typedef vector<char> vChar;
	typedef vector<vchar> vvChar;
	vvChar data;
	unsigned n;

public:
	// 用边长来构造
	Square (unsigned _n) : n(_n) {}

	Square rotateClockwise90() {
		Square tmp(n);
		for (unsigned int i = 0; i data[n - 1 - j][i]);
			}
			tmp.data.push_back(vcTmp);
		}

		return tmp;
	}

	Square rotateClockwise180() {
		return this->rotateClockwise90().rotateClockwise90();
	}

	Square rotateClockwise270() {
		return this->rotateClockwise180().rotateClockwise90();
	}

	Square reflecteHorizontal() {
		Square tmp(n);
		for (unsigned int i = 0; i data[i][n - j - 1]);
			}
			tmp.data.push_back(vcTmp);
		}

		return tmp;	
	}

	bool operator==(const Square &other) const {
		if (this->n != other.n) {
			return false;
		}

		for (unsigned i = 0; i data[i][j] != other.data[i][j]) {
					return false;
				}
			}
		}

		return true;
	}

	friend istream & operator>>(istream& is, Square &s) {
		for (unsigned int i = 0; i > cTmp;
				vcTmp.push_back(cTmp);
			}
			s.data.push_back(vcTmp);
		}

		return is;
	}

	friend ostream & operator= 1) {
				cout = 1) {
					cout > sideLen;
	Square sa(sideLen);
	Square sb(sideLen);
	cin >> sa >> sb;

#ifndef MY_DEBUG
	cout 
<p><br>
</p>
<p><br>
</p>
<p><br>
</p>
<p>附：</p>
<h3>标程</h3>
<p>注：它的旋转函数中坐标变换错了。</p>

<pre class="brush:php;toolbar:false">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAXN 10

typedef struct Board Board;
struct Board {
    int n;
    char b[MAXN][MAXN];
};

/* rotate 90 degree clockwise: [r, c] -> [c, n+1 - r] */
Board
rotate(Board b)
{
    Board nb;
    int r, c;

    nb = b;
    for(r=0; r<b.n r for c nb.b b.b return nb reflect board horizontally:> [r, n-1 -c] */
Board
reflect(Board b)
{
    Board nb;
    int r, c;

    nb = b;
    for(r=0; r<b.n r for c nb.b b.b return nb non-zero if and only boards are equal int eqboard b board bb bb.n bb.b rdboard n b.n="n;" getc assert void main file change fin='fopen("transform.in",' fout='fopen("transform.out",' null fscanf rotate else reflect fprintf exit><br>

<h3>题目</h3>


<center>
<strong><span>Transformations</span></strong><br>
</center>

<p>A square pattern of size N x N (1 
</p>
<ul>
<li>#1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.</li>
<li>#2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.</li>
<li>#3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.</li>
<li>#4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).</li>
<li>#5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).</li>
<li>#6: No Change: The original pattern was not changed.</li>
<li>#7: Invalid Transformation: The new pattern was not obtained by any of the above methods.</li>
</ul>
<p>In the case that more than one transform could have been used, choose the one with the minimum number above.</p>
<h3>PROGRAM NAME: transform</h3>
<h3>INPUT FORMAT</h3>
<table>
<tbody>
<tr>
<td>Line 1:</td>
<td>A single integer, N</td>
</tr>
<tr>
<td>Line 2..N+1:</td>
<td>N lines of N characters (each either `@' or `-'); this is the square before transformation</td>
</tr>
<tr>
<td>Line N+2..2*N+1:</td>
<td>N lines of N characters (each either `@' or `-'); this is the square after transformation</td>
</tr>
</tbody>
</table>
<h3>SAMPLE INPUT (file transform.in)</h3>
<pre class="brush:php;toolbar:false">3
@-@
---
@@-
@-@
@--
--@

OUTPUT FORMAT

A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before' representation to the `after' representation.

SAMPLE OUTPUT (file transform.out)

1