luogu2346|luogu2346 四子连棋 luogu2346四子连棋

题目大意在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。求用最少的步数移动到目标棋局的步数。
【luogu2346|luogu2346 四子连棋】
总体思路很简单，Bfs即可，只是需要注意以下几点：

memcmp的返回值不一定是-1, 0, 1，而是<0, =0, >0的某个数。这在windows和linux上的效果不一样。
注意：黑白双方交替走棋。
任意一方都必须走一步。

#include #include #include #include #include #include using namespace std; const int MAX_N = 10; const int N = 4; const int Dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} }; struct Node { char A[MAX_N][MAX_N]; int Level; char NextColor; Node() { memset(A, 0, sizeof(A)); Level = 0; } Node operator = (const Node& a) { memcpy(A, a.A, sizeof(A)); Level = a.Level; NextColor = a.NextColor; return *this; } bool operator < (const Node& a) const { if (NextColor != a.NextColor) return NextColor == 'B'; else return memcmp(A, a.A, sizeof(A)) < 0; } bool operator == (const Node& a) const { return NextColor == a.NextColor && memcmp(A, a.A, sizeof(A)) == 0; } void OPos1(int &oRow1, int &oCol1) { for (int row = 1; row <= N; row++) for (int col = 1; col <= N; col++) if (A[row][col] == 'O') { oRow1 = row; oCol1 = col; return; } } void OPos2(int &oRow2, int &oCol2) { int oRow1, oCol1; OPos1(oRow1, oCol1); for (int col = oCol1 + 1; col <= N; col++) if (A[oRow1][col] == 'O') { oRow2 = oRow1; oCol2 = col; return; } for (int row = oRow1 + 1; row <= N; row++) for (int col = 1; col <= N; col++) if (A[row][col] == 'O') { oRow2 = row; oCol2 = col; return; } assert(0); } bool CanMove1(const int dRow, const int dCol) { int oRow1, oCol1; OPos1(oRow1, oCol1); int nextRow = oRow1 + dRow, nextCol = oCol1 + dCol; return A[nextRow][nextCol] == NextColor && nextRow <= N && nextRow >= 1 && nextCol <= N && nextCol >= 1; } Node GetMove1(int dRow, int dCol) { int oRow1, oCol1; OPos1(oRow1, oCol1); Node ans = *this; swap(ans.A[oRow1][oCol1], ans.A[oRow1 + dRow][oCol1 + dCol]); return ans; } bool CanMove2(const int dRow, const int dCol) { int oRow2, oCol2; OPos2(oRow2, oCol2); int nextRow = oRow2 + dRow, nextCol = oCol2 + dCol; return A[nextRow][nextCol] == NextColor && nextRow <= N && nextRow >= 1 && nextCol <= N && nextCol >= 1; } Node GetMove2(int dRow, int dCol) { int oRow2, oCol2; OPos2(oRow2, oCol2); Node ans = *this; swap(ans.A[oRow2][oCol2], ans.A[oRow2 + dRow][oCol2 + dCol]); return ans; } bool Ok() { for (int row = 1; row <= N; row++) { char st = A[row][1]; bool ok = true; for (int col = 2; col <= N; col++) if (A[row][col] != st) { ok = false; break; } if (ok) return true; } for (int col = 1; col <= N; col++) { char st = A[1][col]; bool ok = true; for (int row = 2; row <= N; row++) if (A[row][col] != st) { ok = false; break; } if (ok) return true; } char st = A[1][1]; bool ok = true; for (int i = 2; i <= N; i++) if (A[i][i] != st) { ok = false; break; } if (ok) return true; st = A[1][N]; ok = true; for (int row = 2, col = N - 1; row <= N; row++, col--) if (A[row][col] != st) { ok = false; break; } return ok; } }; Node Start; int Bfs() { static queue q; static set cache; Node s1 = Start, s2 = Start; s1.NextColor = 'B'; s2.NextColor = 'W'; q.push(s1); q.push(s2); cache.insert(s1); cache.insert(s2); while (!q.empty()) { Node cur = q.front(); q.pop(); if (!(cur == s1 || cur == s2) && cur.Ok()) return cur.Level; for (int i = 0; i < 4; i++) { if (cur.CanMove1(Dir[i][0], Dir[i][1])) { Node next = cur.GetMove1(Dir[i][0], Dir[i][1]); next.NextColor = (cur.NextColor == 'B' ? 'W' : 'B'); if (!cache.count(next)) { next.Level = cur.Level + 1; cache.insert(next); q.push(next); } } if (cur.CanMove2(Dir[i][0], Dir[i][1])) { Node next = cur.GetMove2(Dir[i][0], Dir[i][1]); next.NextColor = (cur.NextColor == 'B' ? 'W' : 'B'); if (!cache.count(next)) { next.Level = cur.Level + 1; cache.insert(next); q.push(next); } } } } return -1; }int main() { for (int i = 1; i <= 4; i++) scanf("%s", Start.A[i] + 1); printf("%d\n", Bfs()); return 0; }

转载于:https://www.cnblogs.com/headboy2002/p/9665652.html