Last active
December 26, 2015 21:18
-
-
Save eclipselu/7214619 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <queue> | |
#include <iostream> | |
#include <string> | |
#include <cstring> | |
#include <climits> | |
using namespace std; | |
const int rows = 4, cols = 5; | |
int dir[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}}; | |
int board[rows][cols]; // 棋盘: 0 - 白色,1 - 黑色 | |
int flip[rows][cols]; // 是否翻转 | |
int get_color(int i, int j) { | |
int color = board[i][j]; | |
// 上下左右四个方向的棋子翻转都会影响当前棋子的状态 | |
for (int k = 0; k < 5; k++) { | |
int ii = i + dir[k][0], jj = j + dir[k][1]; | |
if (ii >= 0 && ii < rows && jj >= 0 && jj < cols) { | |
color += flip[ii][jj]; | |
} | |
} | |
color = color % 2; | |
return color; | |
} | |
int get_steps() { | |
// 根据第一行的翻转状态,从第二行开始枚举,看哪些需要翻转 | |
for (int i = 1; i < rows; i++) { | |
for (int j = 0; j < cols; j++) { | |
// 如果上一行的对应位置在之前所有翻转结束后是白色的 | |
// 那么本行相应位置的应做翻转 | |
if (get_color(i - 1, j) == 0) { | |
flip[i][j] = 1; | |
} | |
} | |
} | |
// 最后一行应全为黑色才算正确 | |
for (int i = 0; i < cols; i++) { | |
if (get_color(rows - 1, i) == 0) { | |
return INT_MAX; | |
} | |
} | |
int steps = 0; | |
for (int i = 0; i < rows; i++) { | |
for (int j = 0; j < cols; j++) { | |
steps += flip[i][j]; | |
} | |
} | |
return steps; | |
} | |
int sol() { | |
int max_num = 1<<cols; | |
int min_steps = INT_MAX; | |
// 枚举第一行的所有翻转状态,00000~11111,每一个整数代表第一行的一种状态 | |
// 每一位代表一个格子,0为不翻转,1为翻转 | |
for (int i = 0; i < max_num; i++) { | |
memset(flip, 0, sizeof(flip)); | |
for (int j = 0; j < cols; j++) { | |
int idx = cols - j - 1; | |
flip[0][idx] = (i>>j) & 0x01; | |
} | |
int steps = get_steps(); | |
if (steps < min_steps) { | |
min_steps = steps; | |
} | |
} | |
return min_steps; | |
} | |
void solve() { | |
// freopen("/Users/danglu/inputs/input.txt", "r", stdin); | |
int T; | |
cin >> T; | |
while (T--) { | |
for (int i = 0; i < rows; i++) { | |
string str; | |
cin >> str; | |
for (int j = 0; j < str.length(); j++) { | |
board[i][j] = str[j] - '0'; | |
} | |
} | |
int steps = sol(); | |
cout << steps << endl; | |
} | |
} | |
int main() { | |
solve(); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <queue> | |
#include <iostream> | |
#include <string> | |
#include <bitset> | |
#include <cstring> | |
using namespace std; | |
const int rows = 4, cols = 5; | |
const int max_num = 1<<(rows * cols); | |
int all_black = (max_num) - 1; | |
bitset<max_num+1> visited; | |
int dir[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}}; | |
int flip(int status, int x, int y) { | |
for (int i = 0; i < 5; i++) { | |
int xx = x + dir[i][0]; | |
int yy = y + dir[i][1]; | |
if (xx >=0 && xx < rows && yy >=0 && yy < cols) { | |
status ^= 1 << (xx * cols + yy); | |
} | |
} | |
return status; | |
} | |
int sol(int status) { | |
visited.reset(); | |
queue<pair<int, int> > q; | |
q.push(pair<int, int>(status, 0)); | |
visited.set(status); | |
int ans = -1; | |
while (!q.empty()) { | |
pair<int, int> st = q.front(); | |
q.pop(); | |
if (st.first == all_black) { | |
ans = st.second; | |
break; | |
} | |
for (int i = 0; i < rows; i++) { | |
for (int j = 0; j < cols; j++) { | |
int s = flip(st.first, i, j); | |
if (!visited.test(s)) { | |
if (s == all_black) { | |
return st.second + 1; | |
} | |
q.push(pair<int, int>(s, st.second + 1)); | |
visited.set(s); | |
} | |
} | |
} | |
} | |
return ans; | |
} | |
void solve() { | |
// freopen("/Users/danglu/inputs/input.txt", "r", stdin); | |
int T; | |
cin >> T; | |
while (T--) { | |
int status = 0; | |
for (int i = 0; i < rows; i++) { | |
string str; | |
cin >> str; | |
for (int j = 0; j < str.length(); j++) { | |
if (str[j] == '1') | |
status |= 1 << (i * cols + j); | |
} | |
} | |
//cout << status << endl; | |
int res = sol(status); | |
cout << res << endl; | |
} | |
} | |
int main() { | |
solve(); | |
return 0; | |
} |
哈哈 你这个总结很不错啊 我们公司程序员平时文档都用Markdown的
这道题其实暴力法也应该用DFS+递归+DP的,coding会短很多,简单很多。
DFS会快吗?我不大清楚诶 反正我BFS给超时了,我是看到最少
俩字条件反射就顺手写了个BFS的 一开始还写错了 ==
我抽空写写
核心的贪心法则: 我枚举完第一行, 接着可以不必枚举了. 以后很多问题都可以这样想想, 试试行不行得通.
对,其它行的情况可以由棋子之间的制约关系得到,我刚开始也没转过弯来
DFS会快吗?
DFS: 2^20复杂度
正解的复杂度只有2^5 * 20
始终是会挂的,但挂得有态度 ;D
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
呜呜呜
党大的总结就是科学啊
真漂亮,还有表格!
我的想法
暴力
正解给我的启发