【例7-15 UVA-1603】Square Destroyer
2024-08-31 18:39:24
【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
先预处理出所有的正方形(长度为1,2...n的)所包含哪些边。
然后记录每个正方形的应有边长和实际边长(有些边被删掉了);
然后搜的时候,每次找到第一个还是完整的正方形。
枚举删掉它的哪一条边。
然后看看哪些正方形会受到影响。
修改那些受影响的正方形的实际边长。
然后进入下一层。继续搜。
然后回溯影响。
直到所有的正方形都变成不完整的就可以了。
暴力就好。不用加优化。
【代码】
/*
1.Shoud it use long long ?
2.Have you ever test several sample(at least therr) yourself?
3.Can you promise that the solution is right? At least,the main ideal
4.use the puts("") or putchar() or printf and such things?
5.init the used array or any value?
6.use error MAX_VALUE?
7.use scanf instead of cin/cout?
8.whatch out the detail input require
*/
/*
一定在这里写完思路再敲代码!!!
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 150;
int T,n,cnt[N],tot,fullsize[N],realsize[N],ans,totm;
bool contain[N][N];
int GetColumn(int x,int y){
int temp1 = (x-1)*(n+1) + x*n + y;
return temp1;
}
int GetRow(int x,int y){
int temp1 = (x-1)*(n+1) + (x-1)*n +y;
return temp1;
}
int findfirst(){
for (int i = 1;i <= tot;i++)
if (fullsize[i]==realsize[i]) return i;
return -1;
}
void dfs(int dep){
if (dep >= ans) return;
int idx = findfirst();
if (idx==-1){
ans = dep;
return;
}
for (int i = 1;i <= totm;i++)
if (cnt[i] == 1 && contain[idx][i]){
cnt[i] = 0;
for (int j = 1;j <= tot;j++) if (contain[j][i]) realsize[j]--;
dfs(dep+1);
cnt[i] = 1;
for (int j = 1;j <= tot;j++) if (contain[j][i]) realsize[j]++;
}
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> T;
while (T--){
tot = 0;
memset(contain,0,sizeof contain);
memset(fullsize,0,sizeof fullsize);
memset(realsize,0,sizeof realsize);
cin >>n;
totm = 2*n*(n+1);
for (int i = 1;i <= totm;i++) cnt[i] = 1;
int k;cin >> k;
while(k--){
int x;cin >>x;cnt[x] = 0;
}
for (int len = 1;len <= n;len++){
for (int i = 1;i <= n-len+1;i++){
for (int j = 1;j <= n - len+1;j++){
//(i,j)
tot++;
int x;
fullsize[tot] = len*4;
for (int k = 0;k < len;k++){
x = GetColumn(i+k,j);
contain[tot][x] = 1;
realsize[tot]+=cnt[x];
x = GetColumn(i+k,j+len);
contain[tot][x] = 1;
realsize[tot]+=cnt[x];
x = GetRow(i,j+k);
contain[tot][x] = 1;
realsize[tot]+=cnt[x];
x = GetRow(i+len,j+k);
contain[tot][x] = 1;
realsize[tot]+=cnt[x];
}
}
}
}
ans = 1000;
dfs(0);
cout << ans << endl;
}
return 0;
}
最新文章
- python学习笔记(三)
- [转] SSH原理与运用(2):远程操作与端口转发
- java线程之——sleep()与wait()的区别
- .net C# 对虚拟目录IIS的操作
- js获取滚动条距离浏览器顶部,底部的高度,兼容ie和firefox
- 文成小盆友python-num9 socket编程
- 一张图讲解为什么需要自己搭建自己的git服务以及搭建的途径
- Android存储之SQLiteDatbase
- JVM、GC与HashMap
- 源码编译安装bind
- 多线程中join()的用法
- C#,WPF中使用多文本显示数据,并对其数据进行关键字高亮等操作
- Java Mail 实现第三方邮件发送功能
- 关于tensorflow conv2d卷积备忘的一点理解
- 【react】---手动封装一个简易版的redux---【巷子】
- Spring IOC(七)类型推断
- windows平台,实现录音功能详解
- 常用Dos(转)
- python lambda简单介绍
- Android学习之Menu