hdu 4770 Lights Against Dudely(回溯)
2024-09-04 11:07:40
pid=4770" target="_blank" style="">题目链接:hdu 4770 Lights Against Dudely
题目大意:在一个N*M的银行里。有N*M个房间,‘#’代表牢固的房间,‘.‘代表的是脆弱的房间。脆弱的房间个数不会超过15个,如今为了确保安全,要在若干个脆弱的房间上装灯。普通的灯是照亮{0, 0}, {-1, 0}, {0, 1}(和题目中坐标有点出入)。然后能够装一个特殊的,能够照耀
- { {0, 0}, {0, 1}, {1, 0} },
- { {0, 0}, {-1, 0}, {0, -1} },
- { {0, 0}, {0, -1}, {1, 0} }
同一个房间不能够装两栈灯,灯光不能照耀牢固的房间,问说最少须要多少栈灯。
解题思路:dfs+剪枝。暴力枚举放特殊灯的位置,然后将脆弱房间依照i坐标大放前面,相等的将j坐标小的方前面,这样做是为了dfs的时候剪枝,仅仅要碰到一个房间不能放就返回。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200;
const int maxv = 20;
const int INF = 0x3f3f3f3f;
const int dir[4][3][2] = { { {0, 0}, {-1, 0}, {0, 1} },
{ {0, 0}, {0, 1}, {1, 0} },
{ {0, 0}, {-1, 0}, {0, -1} },
{ {0, 0}, {0, -1}, {1, 0} }
};
int ans;
int n, N, M, x[maxv], y[maxv], c[maxv];
int v[maxn+5][maxn+5];
char g[maxn+5][maxn+5];
inline int judge (int xi, int yi, const int d[3][2]) {
for (int i = 0; i < 3; i++) {
int p = xi + d[i][0];
int q = yi + d[i][1];
if (p <= 0 || p > N)
continue;
if (q <= 0 || q > M)
continue;
if (g[p][q] == '#')
return 0;
}
return 1;
}
inline void set (int xi, int yi, const int d[3][2], int type) {
for (int i = 0; i < 3; i++) {
int p = xi + d[i][0];
int q = yi + d[i][1];
if (p <= 0 || p > N)
continue;
if (q <= 0 || q > M)
continue;
v[p][q] = type;
}
}
void init () {
n = 0;
for (int i = 1; i <= N; i++)
scanf("%s", g[i] + 1);
for (int i = N; i; i--) {
for (int j = 1; j <= M; j++) {
if (g[i][j] == '.') {
x[n] = i;
y[n] = j;
n++;
}
}
}
memset(c, 0, sizeof(c));
for (int i = 0; i < n; i++)
c[i] = judge(x[i], y[i], dir[0]);
}
/*
int solve (int spi, int id) {
memset(v, 0, sizeof(v));
int ans = INF;
for (int s = 0; s < (1<<n); s++) {
bool flag = true;
for (int i = 0; i < n; i++) {
if (s&(1<<i) && (c[i] == 0 || i == spi)) {
flag = false;
break;
}
}
if (flag) {
int light = 0;
int tmp = set(x[spi], y[spi], dir[id], 1);
for (int i = 0; i < n; i++) {
if (s&(1<<i)) {
light++;
tmp += set(x[i], y[i], dir[0], 1);
}
}
if (tmp == n)
ans = min(ans, light);
memset(v, 0, sizeof(v));
}
}
return ans+1;
}
*/
void dfs (int d, int f, int cnt) {
if (cnt >= ans)
return;
if (d == n) {
ans = cnt;
return;
}
if (v[x[d]][y[d]])
dfs (d + 1, f, cnt);
if (c[d] && d != f) {
set(x[d], y[d], dir[0], 1);
dfs (d + 1, f, cnt+1);
set(x[d], y[d], dir[0], 0);
}
}
int main () {
while (scanf("%d%d", &N, &M) == 2 && N + M) {
init();
ans = INF;
if (n == 0)
ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
if (judge (x[i], y[i], dir[j])) {
memset(v, 0, sizeof(v));
set(x[i], y[i], dir[j], 1);
dfs(0, i, 1);
set(x[i], y[i], dir[j], 0);
}
}
}
if (ans == INF)
printf("-1\n");
else
printf("%d\n", ans);
}
return 0;
}
最新文章
- Go语言实战 - revel框架教程之用户注册
- Error:(1, 1) error: illegal character: \65279解决方法
- Jquery学习笔记--性能优化建议
- 学习WPF——元素绑定
- java获取本月开始时间和结束时间、上个月第一天和最后一天的时间以及当前日期往前推一周、一个月
- ZOJ 2760 How Many Shortest Path (不相交的最短路径个数)
- html5的video标签支持的视频格式
- aix5.1 5.2 5.3 6.1 7.1运维技术总结
- Spring通过AOP实现对Redis的缓存同步
- SqlServer-COMPUTE BY
- Ubuntu 小白安装血泪史
- CSS后代选择器、子元素选择器、相邻兄弟选择器区别与详解
- Linux上安装二进制文件MySQL详解
- CentOS7.x编译安装zabbix4.0
- 基本数据类型 列表 list
- Mysql基本操作指令集锦
- git切换远程仓库地址
- oracle中实现当前月减少或增加N个月
- vue 路由参数变化,页面不更新的问题
- 解决VS调试Web应用无问题而部署在IIS上报500和403的问题
热门文章
- NOIP模拟&#183;20141105题解
- linux下的udev是干嘛的,能否说的通俗点
- 生成SESSIONID
- Swift之单例模式
- CDHtmlDialog 基本使用
- juqery.fn.extend和jquery.extend
- 《Go语言实战》笔记之第四章 ----数组、切片、映射
- 白话空间统计之:Moran&;#39;s I(莫兰指数)
- http://www.ruanyifeng.com/blog/2013/07/gpg.html
- C#动态调用webservice方法