题意简述

将 $1\sim n\cdot m$ 填入 $n\times m$ 网格。之后进行一个轮流选格子的游戏：先手可以选任意一个，之后每次必须选与已选格子相邻的格子。目标是使后手所选数字之和严格小于先手。

构造思路

核心想法是将网格划分为许多“配对”或“形状”，使得无论先手选哪个格子，后手都能在同一配对或相邻区域中选择一个更小或较大的数字，从而使得后手的总和更小。

预处理

定义方向数组 dx[] = {-1,0,0,1}, dy[] = {0,-1,1,0}。使用 color 数组标记每个格子所属的“配对块”。

情况 1：$n$ 和 $m$ 均为奇数

• 先通过 placePair 将网格前面所有列两两配对，再将最后一列的行两两配对。
• 右下角 (n, m) 填入最大的数 $n\cdot m$（这样先手不会选它，因为选它得不到好处）。
• 游戏时，若交互器选择了某个格子，我们优先选择同一颜色块内的另一个格子（配对格），这样后手总能选到配对的较小数。若配对格已被选，则选一个与已选格子相邻且不是最大值 $n\cdot m$ 的格子即可。
• 此策略保证了后手总和较小。

情况 2：$n$ 或 $m$ 为偶数（且不同时为奇数）

• 首先，如果 $n > m$，则交换行列（逻辑上转置网格），并在输出时交换坐标，使得处理时始终有 $n \le m$。
• 然后根据具体的尺寸放置多个 T 形块 或 水平/垂直配对：
  • T 形块 (placeTShape)：中心放一个较小的数，四周放较大的数，同色。这样无论先手选中心还是四周，后手都可以选同一 T 形块中的另一个适当的格子。
  • 剩余的空间用 fillHorizontalPairs 或 fillVerticalPairs 填满成对格子。
• 游戏交互时，后手同样优先选择与先手所选格子同色且数值更小的格子；如果没有同色未选格，则选相邻的任意格子（事实上配对策略已保证一定有同色格可选）。

关键结论

该构造保证了后手在大多数情况下可以“跟随”先手的步伐，并在每个配对或形状中选择更有利于自己的数字，最终使得后手选择的数字总和严格小于先手。该策略在 $n,m\ge 4$ 时均可实现。

时间复杂度：填数 $O(nm)$，交互 $O(nm)$，完全在 5 秒限制内。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 15;
const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};

int n, m, x, y;
int grid[MAX_N][MAX_N], color[MAX_N][MAX_N], visited[MAX_N][MAX_N];
int currentValue, currentColor, flipCoords;

bool isAdjacent(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= m && visited[nx][ny])
            return true;
    }
    return false;
}

void interact() {
    cin >> x >> y;
    if (flipCoords) swap(x, y);
    visited[x][y] = 1;
}

void output(int x, int y) {
    visited[x][y] = 1;
    if (flipCoords)
        cout << y << ' ' << x << endl;
    else
        cout << x << ' ' << y << endl;
}

void placePair(int x1, int y1, int x2, int y2) {
    grid[x1][y1] = ++currentValue;
    grid[x2][y2] = ++currentValue;
    color[x1][y1] = color[x2][y2] = ++currentColor;
}

void placeTShape(int x, int y) {
    int largestValue = n * m - 12 + currentColor * 3;
    grid[x][y] = ++currentValue;
    color[x][y] = ++currentColor;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
            grid[nx][ny] = ++largestValue;
            color[nx][ny] = currentColor;
        }
    }
}

void printGrid() {
    if (!flipCoords) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                cout << grid[i][j] << ' ';
            cout << endl;
        }
    } else {
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++)
                cout << grid[j][i] << ' ';
            cout << endl;
        }
    }
}

void fillHorizontalPairs() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
            if (!grid[i][j] && !grid[i][j + 1])
                placePair(i, j, i, j + 1);
}

void fillVerticalPairs() {
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
            if (!grid[i][j] && !grid[i + 1][j])
                placePair(i, j, i + 1, j);
}

void solve() {
    cin >> n >> m;
    memset(grid, 0, sizeof(grid));
    memset(color, 0, sizeof(color));
    memset(visited, 0, sizeof(visited));
    currentColor = currentValue = flipCoords = 0;

    if (n % 2 == 1 && m % 2 == 1) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < m; j += 2)
                placePair(i, j, i, j + 1);
        for (int i = 1; i <= n; i += 2)
            placePair(i, m, i + 1, m);
        grid[n][m] = n * m;
        printGrid();
        for (int i = 1; i < n * m; i += 2) {
            interact();
            bool selected = false;
            for (int i1 = 1; i1 <= n; i1++) {
                for (int j1 = 1; j1 <= m; j1++)
                    if (!visited[i1][j1] && color[i1][j1] == color[x][y]) {
                        output(i1, j1);
                        selected = true;
                        break;
                    }
                if (selected) break;
            }
            if (selected) continue;
            for (int i1 = 1; i1 <= n; i1++)
                for (int j1 = 1; j1 <= m; j1++)
                    if (!visited[i1][j1] && isAdjacent(i1, j1) && grid[i1][j1] != n * m) {
                        output(i1, j1);
                        i1 = n; j1 = m; // break out of loops
                    }
        }
        cin >> x >> y; // last turn of interactor
        return;
    }

    if (n > m) {
        swap(n, m);
        flipCoords = 1;
    }
    if (n == 4 && m == 4) {
        placeTShape(1, 2);
        placeTShape(2, 4);
        placeTShape(3, 1);
        placeTShape(4, 3);
    } else if (n == 4 && m == 5) {
        placeTShape(1, 2);
        placeTShape(3, 1);
        placeTShape(3, 5);
        placeTShape(4, 3);
        fillHorizontalPairs();
    } else {
        placeTShape(1, 2);
        placeTShape(3, 1);
        placeTShape(1, m - 1);
        placeTShape(3, m);
        placePair(2, 3, 3, 3);
        placePair(4, 2, 4, 3);
        placePair(2, m - 2, 3, m - 2);
        placePair(4, m - 2, 4, m - 1);
        if (m % 2 == 0)
            fillHorizontalPairs();
        else
            fillVerticalPairs();
    }
    printGrid();
    for (int i = 1; i <= n * m; i += 2) {
        interact();
        pair<int,int> bestMove = {-1, -1};
        for (int i1 = 1; i1 <= n; i1++)
            for (int j1 = 1; j1 <= m; j1++)
                if (!visited[i1][j1] && color[i1][j1] == color[x][y] &&
                    (bestMove.first == -1 || grid[i1][j1] < grid[bestMove.first][bestMove.second]))
                    bestMove = {i1, j1};
        output(bestMove.first, bestMove.second);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}