CoVH之再破难关/黑白棋
Problem
OIBH组织派出的黄金十二人+青铜五小强还没有到, 他们只能指望原先的机关能够阻拦住柯南的脚步.
柯南打开大门之后发现里面还有一个门, 门上还有一个神奇的锁(-,-)
这是一个4*4的锁, 上面有8个凸起的格子和8个被按下的格子
当且仅当两个格子有公共边时, 则称这两个格子是相邻的。
每次操作只能够交换相邻的两个格子
柯南看到了初始锁的状态 和目标锁的状态
同样组织只允许他用最少步数打开锁
输入格式
第1到4行每行四个数字(1或者0),描述了初始锁状态
接着是一个空行
第6到9行每行四个数字,描述了最终锁状态
输出格式
输出文件只有一行,是一个整数n,表示最少的操作次数。
1 2 3 4 5 6 7 8 9 10 11 12
| Input 1111 0000 1110 0010
1010 0101 1010 0101 Output 4
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
|
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; char a[5][5], b[5][5]; int c[9][3], d[9][3], e[9][9], v[9], w = 99999; long long ans, q = 0; void dfs(int t) { if (t == 9) { if (ans < w){ w = ans; return; } } if(ans>w){ return; } for (int i = 1; i <= 8; i++) { if (v[i] == 0) { ans += e[t][i]; v[i] = 1; dfs(t + 1); v[i] = 0; ans -= e[t][i]; } } } int main() { for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++) { cin >> a[i][j]; if (a[i][j] == '1') { q++; d[q][1] = i; d[q][2] = j; } } q = 0; for (int i = 1; i <= 4; i++) for (int j = 1; j <= 4; j++) { cin >> b[i][j]; if (b[i][j] == '1') { q++; c[q][1] = i; c[q][2] = j; } } q = 0; for (int j = 1; j <= 8; j++){
for (int i = 1; i <= 8; i++){ e[i][j] = abs(c[i][1] - d[j][1]) + abs(c[i][2] - d[j][2]);
} } dfs(1); cout << w << endl; return 0; }
|