acmfactorx1.cpp

2004ACM竞赛上海国内赛题部分答案

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Point{
public:
	Point(){x=0;y=0;}
	Point(int a,int b){x=a;y=b;}
	int x;
	int y;
	friend bool Eq(Point a,Point b);
};
bool Eq(Point a,Point b) {
	return ((a.x==b.x)&&(a.y==b.y));
}
vector<Point> v;
int L[]={0,1,3,9,27,81,243,729};
int Loc[]={0,1,2,5,14,41,122,365};
/*int T(int i){
	if(i==1) return 1;
	if(i<=3) return 1;
	if(i<=9) return 1;
	if(i<=27) return 1;
	if(i<=81) return 1;
	if(i<=243) return 1;
	if(i<=729) return 1;
}
int TR(int i){
	if(i<=1) return 1;
	if(i<=3) return 2;
	if(i<=9) return 3;
	if(i<=27) return 4;
	if(i<=81) return 5;
	if(i<=243) return 6;
	if(i<=729) return 7;
}//*/

void INS(int x,int y,int i){
	if(i==0) v.insert(v.end(),Point(x,y));
	else {i--;
		INS(x,y,i);
		INS(x-L[i],y-L[i],i);
		INS(x-L[i],y+L[i],i);
		INS(x+L[i],y-L[i],i);
		INS(x+L[i],y+L[i],i);
	}
}
void Print(int c){
	int i,j;vector<Point>::iterator it;
	for(i=1;i<L[c]+1;i++){
		for(j=1;j<L[c]+1;j++){
			it=v.begin();
			while(it!=v.end()){if(Eq(*it,Point(i,j))) break;it++;}
			if(it!=v.end()) cout<<'X';
			else cout<<' ';
		}
		cout<<endl;
	}
	cout<<'_'<<endl;
}
int main(){
	int c;
	INS(Loc[4],Loc[4],4);
	while(1){
		cin>>c;if(c==0) return 0;
		Print(c);
	}
}