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

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

【黄浩展 25工学院】思路：

先写最简单的左移操作，右移可直接翻转，上移对每列转化为数组进行左移操作，下移为上移翻转，之后递归搜索并更新最大值

#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;
}