[Luogu] Mayan游戏
2024-09-05 07:16:44
https://www.luogu.org/problemnew/show/P1312
太恶心了
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream> using namespace std;
const int N = ; struct Node{int x, y, ho;} answer[N];
int n;
int a[N][N]; inline int read() {
int x = ; char c = getchar();
while(c < '' || c > '')c = getchar();
while(c >= '' && c <= '')x = x * + c - '', c = getchar();
return x;
} void drop() {
int num[N][N];
memset(num, -, sizeof(num));
for(int i = ; i < ; i ++) {
int h = ;
for(int j = ; j < ; j ++) if(a[i][j]) num[i][h ++] = j;
}
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
a[i][j] = num[i][j] == - ? : a[i][num[i][j]];
return ;
} bool empty() {
for(int i = ; i < ; i ++) for(int j = ; j < ; j ++) if(a[i][j]) return ;
return ;
} bool clear() {
bool ret_flag = ;
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
if(a[i][j]) {
int x = i;
while(x < && a[i][j] == a[x + ][j]) x ++;
if(x - i >= ) {
for(int xx = i; xx <= x; xx ++) {
int up = j; int dn = j;
while(a[xx][up + ] == a[i][j] && up < ) up ++;
while(a[xx][dn - ] == a[i][j] && dn > ) dn --;
if(up - dn >= )
for(int y_ = dn; y_ <= up; y_ ++) a[xx][y_] = ;
}
for(int x_ = i; x_ <= x; x_ ++) a[x_][j] = ;
ret_flag = ;
}
}
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
if(a[i][j]) {
int y = j;
while(a[i][y + ] == a[i][j] && y < ) y ++;
if(y - j >= ) {
for(int yy = j; yy <= y; yy ++) {
int lef = i; int rig = i;
while(a[lef - ][yy] == a[i][j] && lef > ) lef --;
while(a[rig + ][yy] == a[i][j] && rig < ) rig ++;
if(rig - lef >= )
for(int x_ = lef; x_ <= rig; x_ ++) a[x_][yy] = ;
}
for(int y_ = j; y_ <= y; y_ ++) a[i][y_] = ;
ret_flag = ;
}
}
if(ret_flag) return ;
else return ;
} void dfs(int tot) {
if(tot > n) {
if(empty()) {
for(int i = ; i <= n; i ++) {
if(answer[i].ho) printf("%d %d %d\n", answer[i].x + , answer[i].y, -);
else printf("%d %d %d\n", answer[i].x, answer[i].y, );
}
exit();
}
return ;
}
int sum[N + ];
memset(sum, , sizeof(sum));
for(int i = ; i < ; i ++) for(int j = ; j < ; j ++) sum[a[i][j]] ++;
for(int i = ; i <= ; i ++) if(sum[i] && sum[i] <= ) return ;
for(int i = ; i < ; i ++)
for(int j = ; j < ; j ++)
if(a[i][j] != a[i + ][j]) {
answer[tot].x = i; answer[tot].y = j; answer[tot].ho = (!a[i][j]);
int tmp[N][N];
memcpy(tmp, a, sizeof(tmp));
swap(a[i][j], a[i + ][j]);
drop();
while(clear()) drop();
dfs(tot + );
answer[tot].x = ; answer[tot].y = ; answer[tot].ho = ;
memcpy(a, tmp, sizeof(a));
}
} int main() {
n = read();
for(int i = ; i < ; i ++) {
for(int j = ; ; j ++) {
a[i][j] = read();
if(!a[i][j]) break;
}
}
dfs();
printf("-1\n");
return ;
}
/*
3
1 0
2 1 0
2 3 4 0
3 1 0
2 4 3 4 0
*/
最新文章
- webapi-crud
- 考虑virtual函数以外的选择
- 关于公司内部的Nuget服务
- uva---(11549)CALCULATOR CONUNDRUM
- c++ struct 使用
- VC 透明滑动控件Slider Control
- sqlserver 查找某个字符在字符串中第N次出现的位置
- DataTables在回调方法中使用api
- has leaked ServiceConnection com.baidu.location.LocationClient
- cmake总结
- 成都大数据Hadoop与Spark技术培训班
- 在同一个系统上装两个不同版本的jdk,配置环境变量不起作用,jdk版本的切换问题
- windows与虚拟机linux能ping通设置
- Java枚举类使用
- 超过1个G免费资源,16套质量超高风格多样的移动UIKIT
- Azure系列2.1.14 —— CopyState
- 如何快速搭建&;配置本地服务器-前端技能
- linux 环境下 firefox乱码问题解决
- Ubuntu 16.04安装idea
- WebConfig 加密解密的原理是什么?
热门文章
- 模块和包,logging模块
- ajax 跨域要点
- Zynq-7000 MiZ701 SOC硬件使用手册
- 【数据结构】P1054 等价表达式
- MQTT图形化客户端比较
- Vue大概知识体系和学习参考
- luogu题解 P3763 【[TJOI2017]DNA】
- arcgis js之地图分屏同步
- Vue-img-preload
- vue使用sass报Modele build failed: TypeError: this.getResolve is not a function at Object.loader...