?

題目傳送門

題意：有n*m的房間，'.'表示可以被點亮，'#'表示不能被點亮，每點亮一個房間會使旁邊的房間也點亮，有意盞特別的燈可以選擇周圍不同方向的房間點亮。問最少需要多少燈使得所有房間點亮

分析：需要被點亮的房間最多只有15個，所以考慮狀壓，然后暴力枚舉選擇哪一個當作特殊燈和枚舉選擇哪個方向使旁邊的房間亮，注意清空vis數組需要優化，memset超時。上交6分鐘1Y，Orz。。。額，看錯榜了，最快的19分鐘，而且這不是第一道水題，汗

?

/************************************************* Author :Running_Time* Created Time :2015/10/22 星期四 18:25:25* File Name :A.cpp************************************************/#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 2e2 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-8; char room[N][N]; struct Point {int x, y;Point (int x, int y) : x (x), y (y) {} }; int n, m; bool vis[N][N];void back_nomal(int x, int y) {vis[x][y] = false;if (x - 1 >= 1) vis[x-1][y] = false;if (y + 1 <= m) vis[x][y+1] = false; }void back_special(int x, int y, int type) {if (type == 1) {back_nomal (x, y); return ;}else if (type == 2) {if (x + 1 <= n) {vis[x+1][y] = false;}if (y + 1 <= m) {vis[x][y+1] = false;}}else if (type == 3) {if (x + 1 <= n) {vis[x+1][y] = false;}if (y - 1 >= 1) {vis[x][y-1] = false;}}else if (type == 4) {if (x - 1 >= 1) {vis[x-1][y] = false;}if (y - 1 >= 1) {vis[x][y-1] = false;}}vis[x][y] = false; }bool light_nomal(int x, int y) {if (x - 1 >= 1 && room[x-1][y] != '.') return false;if (y + 1 <= m && room[x][y+1] != '.') return false;if (x - 1 >= 1) {vis[x-1][y] = true;}if (y + 1 <= m) {vis[x][y+1] = true;}vis[x][y] = true;return true; }bool light_special(int x, int y, int type) {if (type == 1) {return light_nomal (x, y);}else if (type == 2) {if (x + 1 <= n && room[x+1][y] != '.') return false;if (y + 1 <= m && room[x][y+1] != '.') return false;if (x + 1 <= n) {vis[x+1][y] = true;}if (y + 1 <= m) {vis[x][y+1] = true;}}else if (type == 3) {if (x + 1 <= n && room[x+1][y] != '.') return false;if (y - 1 >= 1 && room[x][y-1] != '.') return false;if (x + 1 <= n) {vis[x+1][y] = true;}if (y - 1 >= 1) {vis[x][y-1] = true;}}else if (type == 4) {if (x - 1 >= 1 && room[x-1][y] != '.') return false;if (y - 1 >= 1 && room[x][y-1] != '.') return false;if (x - 1 >= 1) {vis[x-1][y] = true;}if (y - 1 >= 1) {vis[x][y-1] = true;}}vis[x][y] = true;return true; }int main(void) {while (scanf ("%d%d", &n, &m) == 2) {if (!n && !m) break;for (int i=1; i<=n; ++i) {scanf ("%s", room[i] + 1);}int cnt = 0;memset (vis, false, sizeof (vis));vector<Point> V;for (int i=1; i<=n; ++i) {for (int j=1; j<=m; ++j) {if (room[i][j] == '.') {cnt++;V.push_back (Point (i, j));}}}if (cnt == 0) {puts ("0"); continue;}int tot = 1 << cnt;int ans = INF;for (int i=0; i<tot; ++i) {for (int k=0; k<cnt; ++k) {for (int l=1; l<=4; ++l) {bool ok = true;for (int j=0; j<cnt; ++j) {if (i & (1 << j)) {if (j == k) {if (!light_special (V[j].x, V[j].y, l)) {ok = false; break;}}else {if (!light_nomal (V[j].x, V[j].y)) {ok = false; break;}}}}if (!ok) {for (int j=0; j<cnt; ++j) {if (j == k) back_special (V[j].x, V[j].y, l);else back_nomal (V[j].x, V[j].y);}continue;}bool flag = true;for (int j=0; j<cnt; ++j) {int x = V[j].x, y = V[j].y;if (!vis[x][y]) {flag = false; break;}}if (flag) {ans = min (ans, __builtin_popcount (i));}for (int j=0; j<cnt; ++j) {if (j == k) back_special (V[j].x, V[j].y, l);else back_nomal (V[j].x, V[j].y);}}}}printf ("%d\n", ans == INF ? -1 : ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/Running-Time/p/4902677.html

總結

以上是生活随笔為你收集整理的状态压缩 + 暴力 HDOJ 4770 Lights Against Dudely的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。