Solutions CS101

Appearance

T20052: 最大点数（同2048规则） ​

dfs, matrices, http://cs101.openjudge.cn/pctbook/T20052/

【黄浩展 25工学院】思路：先写最简单的左移操作，右移可直接翻转，上移对每列转化为数组进行左移操作，下移为上移翻转，之后递归搜索并更新最大值

cpp
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void mergeleft(vector<int>& line) {
	vector<int>nxt, tmp;
	for (int n : line)
		if (n != 0)
			nxt.push_back(n);
	line = vector<int>(line.size(), 0);
	for (int i = 0; i < nxt.size();) {
		if (i + 1 < nxt.size() && nxt[i] == nxt[i + 1]) {
			tmp.push_back(2 * nxt[i]);
			i += 2;
		}
		else {
			tmp.push_back(nxt[i]);
			i++;
		}
	}
	for(int i=0;i<tmp.size();i++)
		line[i] = tmp[i];
}

void mergeright(vector<int>& line) {
	reverse(line.begin(), line.end());
	mergeleft(line);
	reverse(line.begin(), line.end());
}

void ml(vector <vector<int>>& grid) {
	for (auto &r : grid)
		mergeleft(r);
}

void mr(vector<vector<int>>& grid) {
	for (auto &r : grid)
		mergeright(r);
}

void mu(vector<vector<int>>& grid) {
	for (int i = 0; i < grid[0].size(); i++) {
		vector<int>tmp;
		for (int j = 0; j < grid.size(); j++)
			tmp.push_back(grid[j][i]);
		mergeleft(tmp);
		for (int k = 0; k < grid.size(); k++)
			grid[k][i] = (k<tmp.size()?tmp[k]:0);
	}
}

void md(vector<vector<int>>& grid) {
	reverse(grid.begin(), grid.end());
	mu(grid);
	reverse(grid.begin(), grid.end());
}

int findmax(vector<vector<int>>& grid) {
	int res = 0, m = grid.size(), n = grid[0].size();
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			res = max(res, grid[i][j]);
	return res;
}

void dfs(vector<vector<int>>& grid, int step, int& ans, int p) {
	ans = max(ans, findmax(grid));
	if (step == p) return;
	vector<vector<int>>tl = grid, tr = grid, tu = grid, td = grid;
	ml(tl);
	if(tl!= grid)
		dfs(tl, step + 1, ans, p);
	mr(tr);
	if (tr!= grid)
		dfs(tr, step + 1, ans, p);
	mu(tu);
	if (tu!= grid)
		dfs(tu, step + 1, ans, p);
	md(td);
	if (td!= grid)
		dfs(td, step + 1, ans, p);
}

int main() {
	int m, n, p; 
	cin >> m >> n >> p;
	vector<vector<int>>grid(m, vector<int>(n));
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> grid[i][j];
	int ans = 0;
	dfs(grid, 0, ans, p);
	cout << ans << endl;
	return 0;
}

【江昊中 25数院】思路：一开始觉得题里给的left函数不够优雅, 于是自己重写了一个, 并写了一个统一的滑动接口. 提交后WA, 以为是dfs出错了, 调了二十多分钟才意识到自己的left的移动算法写错了

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

using Board = vector<vector<int>>;

// 左右反转矩阵
void reverseRow(Board& board) {
    for (auto& row : board) {
        reverse(row.begin(), row.end());
    }
}

// 转置矩阵
void transpose(Board& board) {
    int n = board.size();
    int m = board[0].size();
    Board tmp(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            tmp[i][j] = board[j][i];
        }
    }
    board = move(tmp);
}

bool left(Board& board) {
    bool changed = false;
    int n = board.size();
    int m = board[0].size();
    for (auto& row : board) {
        // 使用快慢指针将非零元素移动到左侧
        int blank_idx = 0;
        for (int j = 0; j < m; j++) {
            if (row[j]) {
                if (blank_idx != j) {
                    row[blank_idx] = row[j];
                    row[j] = 0;
                    changed = true;
                }
                blank_idx++;
            }
        }

        for (int j = 0; j < m - 1; j++) {
            if (row[j] && row[j + 1] == row[j]) {
                row[j] <<= 1;
                row[j + 1] = 0;
                changed = true;
            }
        }

        blank_idx = 0;
        for (int j = 0; j < m; j++) {
            if (row[j]) {
                if (blank_idx != j) {
                    row[blank_idx] = row[j];
                    row[j] = 0;
                    changed = true;
                }
                blank_idx++;
            }
        }
    }
    return changed;
}

bool right(Board& board) {
    reverseRow(board);
    bool changed = left(board);
    reverseRow(board);
    return changed;
}

bool up(Board& board) {
    transpose(board);
    bool changed = left(board);
    transpose(board);
    return changed;
}

bool down(Board& board) {
    transpose(board);
    bool changed = right(board);
    transpose(board);
    return changed;
}

enum class Direction {
    LEFT,
    RIGHT,
    UP,
    DOWN
};

// 统一的滑动接口
bool slide(Board& board, Direction dir) {
    switch (dir) {
        case Direction::LEFT:
            return left(board);
        case Direction::RIGHT:
            return right(board);
        case Direction::UP:
            return up(board);
        case Direction::DOWN:
            return down(board);
        default:
            return false;
    }
}   

int const max_num(const Board& board) {
    int res = 0;
    for (const auto& row : board) {
        for (int num : row) {
            res = max(res, num);
        }
    }
    return res;
}

int global_max = 0;
// 深度优先搜索枚举所有可能的操作序列,并记录最大值
void dfs(Board& board, int p, int cur_step) {
    if (cur_step == p) {
        global_max = max(global_max, max_num(board));
        return;
    }

    Direction dirs[] = {Direction::LEFT, Direction::RIGHT, Direction::UP, Direction::DOWN};
    for (Direction dir : dirs) {
        Board tmp = board;
        if (slide(tmp, dir)) {
            dfs(tmp, p, cur_step + 1);
        } else {
            global_max = max(global_max, max_num(tmp));
        }
    }
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    Board board(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    dfs(board, p, 0);
    cout << global_max << endl;
    return 0;
}

用时60min