USACO1.2.2Transformations（模拟）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了USACO1.2.2Transformations（模拟），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7128字，纯文字阅读大概需要11分钟。

内容图文

分析 这是我第一次在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 
#include 
#include 
#include 
#include 
#include 
using namespace std;

class Square {
private:
	typedef vector vChar;
	typedef vector vvChar;
	vvChar data;
	unsigned n;

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

	Square rotateClockwise90() {
		Square tmp(n);
		for (unsigned int i = 0; i < tmp.n; ++i) {
			Square::vChar vcTmp;			
			for (unsigned int j = 0; j < tmp.n; ++j){
				vcTmp.push_back(this->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 < tmp.n; ++i) {
			Square::vChar vcTmp;			
			for (unsigned int j = 0; j < tmp.n; ++j){
				vcTmp.push_back(this->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 < n; ++i) {
			for (unsigned j = 0; j < n; ++j) {
				if (this->data[i][j] != other.data[i][j]) {
					return false;
				}
			}
		}

		return true;
	}

	friend istream & operator>>(istream& is, Square &s) {
		for (unsigned int i = 0; i < s.n; ++i) {
			Square::vChar vcTmp;			
			for (unsigned int j = 0; j < s.n; ++j){
				char cTmp;
				cin >> cTmp;
				vcTmp.push_back(cTmp);
			}
			s.data.push_back(vcTmp);
		}

		return is;
	}

	friend ostream & operator<<(ostream& os, const Square &s) {
		for (unsigned int i = 0; i < s.n; ++i) {
			if (i >= 1) {
				cout << endl;
			}
			for (unsigned int j = 0; j < s.n; ++j){
				if (j >= 1) {
					cout << " ";
				}
				cout << s.data[i][j];		
			}
		}

		return os;
	}
};




int main()
{
#ifndef ONLINE_JUDGE
	freopen("transform.in", "r", stdin);
	freopen("transform.out", "w", stdout);
#endif

	unsigned sideLen;
	cin >> sideLen;
	Square sa(sideLen);
	Square sb(sideLen);
	cin >> sa >> sb;

#ifndef MY_DEBUG
	cout << "sa=\n" << sa << "\n" << endl;
	cout << "sb=\n" << sb << "\n" << endl;
	assert(sa.rotateClockwise270() == sa.rotateClockwise90().rotateClockwise90().rotateClockwise90());
#endif

	if (sa.rotateClockwise90() == sb) {
		cout << "1" << endl;
		return 0;
	}

	if (sa.rotateClockwise180() == sb) {
		cout << "2" << endl;
		return 0;
	}

	if (sa.rotateClockwise270() == sb) {
		cout << "3" << endl;
		return 0;
	}

	if (sa.reflecteHorizontal() == sb) {
		cout << "4" << endl;
		return 0;
	}

	Square saRe(sa.reflecteHorizontal());
	if (saRe.rotateClockwise90() == sb
		|| saRe.rotateClockwise180() == sb
		|| saRe.rotateClockwise270() == sb) {
		cout << "5" << endl;
		return 0;
	}

	if (sa == sb) {
		cout << "6" << endl;
		return 0;
	}

	cout << "7" << endl;
	return 0;
}

附：

标程

注：它的旋转函数中坐标变换错了。

#include 
#include 
#include 
#include 

#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=0; c<b.n; c++)
        nb.b[c][b.n+1 - r] = b.b[r][c];

    return nb;
}

/* reflect board horizontally: [r, c] -> [r, n-1 -c] */
Board
reflect(Board b)
{
    Board nb;
    int r, c;

    nb = b;
    for(r=0; r<b.n; r++)
    for(c=0; c<b.n; c++)
        nb.b[r][b.n-1 - c] = b.b[r][c];

    return nb;
}

/* return non-zero if and only if boards are equal */
int
eqboard(Board b, Board bb)
{
    int r, c;

    if(b.n != bb.n)
        return 0;

    for(r=0; r<b.n; r++)
    for(c=0; c<b.n; c++)
        if(b.b[r][c] != bb.b[r][c])
            return 0;
    return 1;
}

Board
rdboard(FILE *fin, int n)
{
    Board b;
    int r, c;

    b.n = n;
    for(r=0; r<n; r++) {
        for(c=0; c<n; c++)
            b.b[r][c] = getc(fin);
        assert(getc(fin) == '\n');
    }
    return b;
}

void
main(void)
{
    FILE *fin, *fout;
    Board b, nb;
    int n, change;

    fin = fopen("transform.in", "r");
    fout = fopen("transform.out", "w");
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%d\n", &n);
    b = rdboard(fin, n);
    nb = rdboard(fin, n);

    if(eqboard(nb, rotate(b)))
        change = 1;
    else if(eqboard(nb, rotate(rotate(b))))
        change = 2;
    else if(eqboard(nb, rotate(rotate(rotate(b)))))
        change = 3;
    else if(eqboard(nb, reflect(b)))
        change = 4;
    else if(eqboard(nb, rotate(reflect(b)))
         || eqboard(nb, rotate(rotate(reflect(b))))
         || eqboard(nb, rotate(rotate(rotate(reflect(b))))))
        change = 5;
    else if(eqboard(nb, b))
        change = 6;
    else
        change = 7;

    fprintf(fout, "%d\n", change);

    exit(0);
}

题目

A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

• #1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
• #2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
• #3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
• #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).
• #5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
• #6: No Change: The original pattern was not changed.
• #7: Invalid Transformation: The new pattern was not obtained by any of the above methods.

In the case that more than one transform could have been used, choose the one with the minimum number above.

PROGRAM NAME: transform

INPUT FORMAT

SAMPLE INPUT (file transform.in)

3
@-@
---
@@-
@-@
@--
--@

OUTPUT FORMAT

SAMPLE OUTPUT (file transform.out)

1

内容总结

以上是互联网集市为您收集整理的USACO1.2.2Transformations（模拟）全部内容，希望文章能够帮你解决USACO1.2.2Transformations（模拟）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端