1 条题解

  • 0
    @ 2025-4-8 20:34:00

    三维井字棋游戏分析与解题思路

    题目分析

    问题描述

    • 游戏在n×n×nn×n×n的三维棋盘上进行
    • 两名玩家交替在(x,y)(x,y)坐标放置球体（黑方先手）
    • 球体遵循重力规则自动落在相应柱子的顶端
    • 胜利条件：首个形成长度≥mm的同色球序列的玩家获胜
    • 序列方向包括：
      • 轴向（x/y/zx/y/z轴，共3种）
      • 面对角线（棋盘表面对角线，共6种）
      • 体对角线（三维空间对角线，共4种）

    关键参数

    参数 范围 说明
    nn 3≤n≤73≤n≤7 棋盘尺寸
    mm 3≤m≤n3≤m≤n 获胜序列长度
    pp 1≤p≤n31≤p≤n^3 总移动步数

    解题思路

    核心算法

    1. 数据结构：

      • 使用三维数组board[n][n][n3]board[n][n][n^3]存储棋盘状态
      • 初始值设为−1-1，表示空位

    2. 落子处理：

      void put_chess(int x, int y, int id) {
    int z = 1;
    while(board[x][y][z] != -1) z++;
    board[x][y][z] = id;  // id=0(黑)或1(白)
    maxz = max(maxz, z);  // 记录当前最大高度
}

    3. 胜负判断：

      • 轴向检查（check_onecheck\_one）：
        • 检查xx,yy,zz三个方向的连续同色球
      • 面对角线检查（check_twocheck\_two）：
        • 检查xyxy,xzxz,yzyz三个平面内的对角线
      • 体对角线检查（check_threecheck\_three）：
        • 检查三维空间对角线（如(1,1,1)→(2,2,2)→...(1,1,1)→(2,2,2)→...）

    4. 主流程：

      while(游戏未结束 && 还有移动步数){
    1. 处理当前落子
    2. 更新棋盘状态
    3. 检查所有可能的获胜序列
    if(发现获胜序列){
        记录获胜方和步数
        标记游戏结束
    }
    切换玩家
}

    复杂度分析

    • 时间复杂度：O(p⋅n⋅m⋅13)O(p \cdot n \cdot m \cdot 13)
      （1313种方向检查，每种最多检查mm个位置）
    • 空间复杂度：O(n3)O(n^3)

    输入输出示例

    输入

    4 3 15
1 1
2 2
1 1
3 3
...（共15行）
0 0 0

    输出

    Black 15

    标程

    #include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
 
#define sz(v) ((int)(v).size())
#define rep(i, n) for(int i = 0; i < n; i++)
#define repf(i, a, b) for(int i = a; i <= b; i++)
#define repd(i, a, b) for(int i = a; i >= b; i--)
#define out(n) printf("%d\n", n)
#define mset(a, b) memset(a, b, sizeof(a))
#define wh(n) while(1 == scanf("%d", &n))
#define whz(n) while(1 == scanf("%d", &n) && n != 0)
#define lint long long
 
using namespace std;
 
const int INF = 1 << 30;
 
const int MaxN = 10;
 
int board[MaxN][MaxN][MaxN * MaxN * MaxN];
int n, m, p;
int maxz;
 
void put_chess(int x, int y, int id)
{
    int z = 1;
    while(board[x][y][z] != -1) z++;
    board[x][y][z] = id;
    if(z > maxz) maxz = z;
}
 
int check_one()
{
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 1;  k <= maxz; k++) {
                int kk = k;
                int total = 0;
                int id = board[i][j][kk];
                if(id == -1) break;
                while(kk <= maxz && board[i][j][kk] == id) {
                    total++;
                    kk++;
                }
                if(total >= m && id != -1) return id;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int k = 1; k <= maxz; k++) {
            for(int j = 1; j <= n; j++) {
                int jj = j;
                int total = 0;
                int id = board[i][jj][k];
                if(id == -1) continue;
                while(jj <= n && board[i][jj][k] == id) {
                    total++;
                    jj++;
                }
                if(total >= m && id != -1) return id;
            }
        }
    }
    for(int j = 1; j <= n; j++) {
        for(int k = 1; k <= maxz; k++) {
            for(int i = 1; i <= n; i++) {
                int ii = i;
                int total = 0;
                int id = board[ii][j][k];
                if(id == -1) continue;
                while(ii <= n && board[ii][j][k] == id) {
                    total++;
                    ii++;
                }
                if(total >= m && id != -1) return id;
            }
        }
    }
    return -1;
}
 
int check_two()
{
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
            int jj = j, kk = k;
            int id = board[i][jj][kk];
            int total = 0;
            if(id == -1) continue;
            while(id == board[i][jj][kk] && jj <= n && kk <= maxz) {
                total++;
                jj++; kk++;
            }
            if(total >= m && id != -1) return id;
        }
        for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
            int jj = j, kk = k;
            int id = board[i][jj][kk];
            int total = 0;
            if(id == -1) continue;
            while(jj >= 1 && kk <= maxz && id == board[i][jj][kk]) {
                total++;
                jj--; kk++;
            }
            if(total >= m && id != -1) return id;
        }
    }
    for(int j = 1; j <= n; j++) {
        for(int i = 1; i <= n; i++) for(int k = 1; k <= maxz; k++) {
            int ii = i, kk = k;
            int id = board[ii][j][kk];
            int total = 0;
            if(id == -1) continue;
            while(id == board[ii][j][kk] && ii <= n && kk <= maxz) {
                total++;
                ii++; kk++;
            }
            if(total >= m && id != -1) return id;
        }
        for(int i = 1; i <= n; i++) for(int k = 1; k <= maxz; k++) {
            int ii = i, kk = k;
            int id = board[ii][j][kk];
            int total = 0;
            if(id == -1) continue;
            while(ii >= 1 && kk <= maxz && id == board[ii][j][kk]) {
                total++;
                ii--; kk++;
            }
            if(total >= m && id != -1) return id;
        }
    }
    for(int k = 1; k <= maxz; k++) {
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
            int ii = i, jj = j;
            int id = board[ii][jj][k];
            int total = 0;
            if(id == -1) continue;
            while(id == board[ii][jj][k] && ii <= n && jj <= n) {
                total++;
                ii++; jj++;
            }
            if(total >= m && id != -1) return id;
        }
        for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
            int ii = i, jj = j;
            int id = board[ii][jj][k];
            int total = 0;
            if(id == -1) continue;
            while(ii >= 1 && jj <= n && id == board[ii][jj][k]) {
                total++;
                ii--; jj++;
            }
            if(total >= m && id != -1) return id;
        }
    }
    return -1;
}
 
int check_three()
{
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii <= n && jj <= n && kk <= maxz && board[ii][jj][kk] == id) {
            total++;
            ii++, jj++, kk++;
        }
        if(total >= m && id != -1) return id;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii <= n && jj >= 0 && kk <= maxz && board[ii][jj][kk] == id) {
            total++;
            ii++, jj--, kk++;
        }
        if(total >= m && id != -1) return id;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii <= n && jj <= n && kk >= 0 && board[ii][jj][kk] == id) {
            total++;
            ii++, jj++, kk--;
        }
        if(total >= m && id != -1) return id;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii <= n && jj >= 0 && kk >= 0 && board[ii][jj][kk] == id) {
            total++;
            ii++, jj--, kk--;
        }
        if(total >= m && id != -1) return id;
    }
    
    
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii >= 0 && jj <= n && kk <= maxz && board[ii][jj][kk] == id) {
            total++;
            ii--, jj++, kk++;
        }
        if(total >= m && id != -1) return id;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii >= 0 && jj >= 0 && kk <= maxz && board[ii][jj][kk] == id) {
            total++;
            ii--, jj--, kk++;
        }
        if(total >= m && id != -1) return id;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][k];
        if(-1 == id) continue;
        int total = 0;
        while(ii >= 0 && jj <= n && kk >= 0 && board[ii][jj][kk] == id) {
            total++;
            ii--, jj++, kk--;
        }
        if(total >= m && id != -1) return id;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= maxz; k++) {
        int ii = i, jj = j, kk = k;
        int id = board[ii][jj][kk];
        if(-1 == id) continue;
        int total = 0;
        while(ii >= 0 && jj >= 0 && kk >= 0 && board[ii][jj][kk] == id) {
            total++;
            ii--, jj--, kk--;
        }
        if(total >= m && id != -1) return id;
    }
    return -1;
}
 
int check_board()
{
    int res = -1;
    res = check_one();
    if(res != -1) return res;
    res = check_two();
    if(res != -1) return res;
    res = check_three();
    if(res != -1) return res;
    return -1;
}
 
int main()
{
    while(3 == scanf("%d%d%d", &n, &m, &p)) {
        if(0 == n && 0 == m && 0 == p) break;
        int id = 1;
        int total;
        bool f = false;
        mset(board, -1);
        maxz = 0;
        int res;
        for(int i = 0; i < p; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            if(!f) {
                put_chess(x, y, id);
                res = check_board();
                if(res != -1) {
                    f = true;
                    total = i + 1;
                }
                id ^= 1;
            }
        }
        if(f) {
            if(res == 1) printf("Black %d\n", total);
            else printf("White %d\n", total);
        }
        else puts("Draw");
    }
    return 0;
}
    • 1

    Make a Sequence

    信息

    ID
    1144
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者
    1. 评测队列
    2. 服务状态
    3. 兼容模式
    4. 主题
    2. 黔ICP备2023002402号-2
    3. Worker 0, 39ms
    4. Powered by Hydro v4.19.1 Community, Modified by 33DAI