广搜
#include#include #include #include #include #define maxn 10010#define inf 1000000007#define ll long longusing namespace std;int n, m, ans = inf;int dx[5] = { 0, 0, 1, -1, 0};int dy[5] = { 0, 1, 0, 0, -1};struct Node { int a[5][5]; int color; int step;} t;queue q;bool check(Node f) { for(int i = 1; i <= 4; i ++) { if(f.a[i][1] == f.a[i][2] && f.a[i][1] == f.a[i][3] && f.a[i][1] == f.a[i][4]) return 1; if(f.a[1][i] == f.a[2][i] && f.a[1][i] == f.a[3][i] && f.a[1][i] == f.a[4][i]) return 1; } if(f.a[1][1] == f.a[2][2] && f.a[1][1] == f.a[3][3] && f.a[1][1] == f.a[4][4]) return 1; if(f.a[1][4] == f.a[3][2] && f.a[1][4] == f.a[2][3] && f.a[1][4] == f.a[4][1]) return 1; return 0;}void init() { //处理一开始的棋子颜色 t.step = 0; t.color = 2; for(int i = 1; i <= 4; i ++) for(int j = 1; j <= 4; j ++) if(t.a[i][j] == 2) for(int k = 1; k <= 4; k ++) { int x = i + dx[k]; int y = j + dy[k]; if(t.a[x][y] == 2) continue ; if(x >= 1 && x <= 4 && y >= 1 && y <= 4) { //注意边界 Node c = t; c.color = t.a[x][y]; c.step = 1; swap(c.a[i][j], c.a[x][y]);//移动棋子 q.push(c); } }}void bfs() { //广搜模板 while(!q.empty()) { Node b = q.front(); q.pop(); if(check(b)) { ans = b.step; return ; } for(int i = 1; i <= 4; i ++) for(int j = 1; j <= 4; j ++) { if(b.a[i][j] == 2) { for(int k = 1; k <= 4; k ++) { int x = i + dx[k]; int y = j + dy[k]; if(x >= 1 && x <= 4 && y >= 1 && y <= 4 && b.a[x][y] == (b.color ^ 1)) { //黑白交替移动 Node c = b; swap(c.a[i][j], c.a[x][y]);//移动棋子 c.color = b.color ^ 1;//如果上一步走的是黑，这一步就是白，上一步是白，这一步是黑。 c.step = b.step + 1;//步数加一 q.push(c);//将当前状态入队 } } } } }}int main() { int x, y, z; char s[10]; for(int i = 1; i <= 4; i ++) { scanf("%s",s+1); for(int j = 1; j <= 4; j ++) { //处理图，便于广搜 if(s[j] == 'B') t.a[i][j] = 1; if(s[j] == 'W') t.a[i][j] = 0; if(s[j] == 'O') t.a[i][j] = 2; } } init(); bfs(); printf("%d\n", ans); return 0;}