P1228 地毯填补问题 求各位大佬调
  • 板块学术版
  • 楼主TangHarry
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/20 17:42
  • 上次更新2024/11/20 19:51:29
查看原帖
P1228 地毯填补问题 求各位大佬调
1258376
TangHarry楼主2024/11/20 17:42
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
int step = 0;
struct node {
	int x, y;
};
int a[1100][1100];
void tian(int leftx, int lefty, int n, int lingx, int lingy) {
	step++;
	int midx, midy;
	midx = leftx + n / 2 - 1;
	midy = lefty + n / 2 - 1;
	if (lingx < leftx + n / 2 && lingy < lefty + n / 2) {
		a[midx + 1][midy] = step;
		a[midx][midy + 1] = step;
		a[midx + 1][midy + 1] = step;
		if (n > 2) {
			tian(leftx, lefty, n / 2, lingx, lingy);								//左上
			tian(leftx, lefty + n / 2, n / 2, leftx + n / 2 - 1, lefty + n / 2);	//右上
			tian(leftx + n / 2, lefty, n / 2, leftx + n / 2, lefty + n / 2 - 1);	//左下
			tian(leftx + n / 2, lefty + n / 2, n / 2, leftx + n / 2, lefty + n / 2);//右下
		}
	}
	if (lingx < leftx + n / 2 && lingy >= lefty + n / 2) {
		a[midx][midy] = step;
		a[midx + 1][midy] = step;
		a[midx + 1][midy + 1] = step;
		if (n > 2) {
			tian(leftx, lefty, n / 2, leftx + n / 2 - 1, lefty + n / 2 - 1);		//左上
			tian(leftx, lefty + n / 2, n / 2, lingx, lingy);						//右上
			tian(leftx + n / 2, lefty, n / 2, leftx + n / 2, lefty + n / 2 - 1);	//左下
			tian(leftx + n / 2, lefty + n / 2, n / 2, leftx + n / 2, lefty + n / 2);//右下
		}
	}
	if (lingx >= leftx + n / 2 && lingy < lefty + n / 2) {
		a[midx][midy] = step;
		a[midx][midy + 1] = step;
		a[midx + 1][midy + 1] = step;
		if (n > 2) {
			tian(leftx, lefty, n / 2, leftx + n / 2 - 1, lefty + n / 2 - 1);		//左上
			tian(leftx, lefty + n / 2, n / 2, leftx + n / 2 - 1, lefty + n / 2);	//右上
			tian(leftx + n / 2, lefty, n / 2, lingx, lingy);						//左下
			tian(leftx + n / 2, lefty + n / 2, n / 2, leftx + n / 2, lefty + n / 2);//右下
		}
	}
	if (lingx >= leftx + n / 2 && lingy >= lefty + n / 2) {
		a[midx][midy] = step;
		a[midx][midy + 1] = step;
		a[midx + 1][midy] = step;
		if (n > 2) {
			tian(leftx, lefty, n / 2, leftx + n / 2 - 1, lefty + n / 2 - 1);		//左上
			tian(leftx, lefty + n / 2, n / 2, leftx + n / 2 - 1, lefty + n / 2);	//右上
			tian(leftx + n / 2, lefty, n / 2, leftx + n / 2, lefty + n / 2 - 1);	//左下
			tian(leftx + n / 2, lefty + n / 2, n / 2, lingx, lingy);				//右下
		}
	}
}
bool cmp(node x, node y) {
	if (x.x != y.x) return x.x < y.x;
	else return x.y < y.y;
}
void one(int t1, int t2, int t3, int t4, int t5, int t6) {
	printf("%d %d 1\n", t5, t6);
} 
void two(int t1, int t2, int t3, int t4, int t5, int t6) {
	printf("%d %d 2\n", t3, t4);
}
void three(int t1, int t2, int t3, int t4, int t5, int t6) {
	printf("%d %d 3\n", t3, t4);
}
void four(int t1, int t2, int t3, int t4, int t5, int t6) {
	printf("%d %d 4\n", t1, t2);
}
int main() {
	int n, x, y, k;
	scanf("%d\n%d %d", &k, &x, &y);
	a[x][y] = 0;
	n = 1;
	for (int i = 1; i <= k; i++) {
		n *= 2;
	}
	tian(1, 1, n, x, y);
	int ma = n * n / 3;
	for (int i = 1; i <= ma; i++) {
		node temp[10];
		int tmp = 1;
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (a[j][k] == i) {
					temp[tmp++] = {j, k};
				}
			}
		}
		sort(temp + 1, temp + 4, cmp);
		int t1 = temp[1].x, t2 = temp[1].y, t3 = temp[2].x, t4 = temp[2].y, t5 = temp[3].x, t6 = temp[3].y;
		if (t1 == t3 && t2 == t4 - 1 && t4 == t6 && t1 == t5 - 1) {
			three(t1, t2, t3, t4, t5, t6);
		} else if (t5 == t3 && t2 == t6 && t4 == t6 - 1 && t1 == t5 - 1) {
			one(t1, t2, t3, t4, t5, t6);
		} else if (t1 == t3 - 1 && t2 == t4 && t3 == t5 && t4 == t6 - 1) {
			two(t1, t2, t3, t4, t5, t6);
		} else if (t1 == t3 && t2 == t4 - 1 && t2 == t6 && t1 == t5 - 1) {
			four(t1, t2, t3, t4, t5, t6);
		}
	}
	return 0;
}
70分,3个TLE
2024/11/20 17:42
加载中...