今日头条笔试解题报告(10.17)
ACM 

头条的笔试还挺有意思的。

推箱子

这题跟走迷宫问题本质上是一致的,只不过状态既要保存人的位置也要保存箱子的位置。直接爆搜就能过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
char mp[55][55];
bool used[55][55][55][55];
int n, m;
struct Point {
	int x, y;
}you, st, ed;

struct State {
	int x, y, xx, yy, step;
	State() { step = 0; };
	State(int x, int y, int xx, int yy,int step)  {
		this->x = x;
		this->y = y;
		this->xx = xx;
		this->yy = yy;
		this->step = step;
	}
	State(Point a, Point b) {
		x = a.x;
		y = a.y;
		xx = b.x;
		yy = b.y;
		step = 0;
	}
};

int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
bool valid(int x, int y) {
	if (x<1 || x>n ) return false;
	if (y<1 || y>m ) return false;
	if (mp[x][y] == '#') return false;
	return true;
}

int bfs() {
	queue<State>Q;
	memset(used, 0, sizeof(used));
	State start(you,st);
	Q.push(start);
	used[start.x][start.y][start.xx][start.yy] = 1;
	while (!Q.empty()) {
		State cur = Q.front();
		if (cur.xx == ed.x && cur.yy == ed.y) return cur.step;
		for (int i = 0; i < 4; i++) {
			int x = cur.x + dir[i][0];
			int y = cur.y + dir[i][1];
			int xx = cur.xx;
			int yy = cur.yy;
			if (!valid(x, y))continue;
			if (x == cur.xx && y == cur.yy) {
				xx = cur.xx + dir[i][0];
				yy = cur.yy + dir[i][1];
			}
			if (!valid(xx, yy)) continue;

			if (xx == ed.x && yy == ed.y) {
				return cur.step + 1;
			}
			if (!used[x][y][xx][yy]) {
				used[x][y][xx][yy] = 1;
				Q.push(State(x, y, xx, yy,cur.step + 1));
			}
		}
		Q.pop();
	}
	return -1;
}
int main() {
	while (cin>>n>>m) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> mp[i][j];
				if (mp[i][j] == 'S') {
					you.x = i;
					you.y = j;
				}
				if (mp[i][j] == '0') {
					st.x = i;
					st.y = j;
				}
				if (mp[i][j] == 'E') {
					ed.x = i;
					ed.y = j;
				}
			}
		}
		cout << bfs() << endl;
	}
}
/*
3 6
.S#..E
.#.0..
......
*/

房间重排

设有n个房间,将第i个房间的人取出来,依次重新安排到i+1,i+2,…1,2,3的房间,不断循环。给你最终各房间人数和最后安排的房间,求最开始的各个房间中人数。

这题有多解,special judge。基本思路就是找到一个包含人数最少的房间,从这个房间开始逆推还原。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n, m;
long long a[111111], b[111111];
vector<int>vt;

bool check(int mIndex) {
	for (int i = 0; i < n; i++) {
		if (i == mIndex) b[i] = n * a[i];
		else b[i] = a[i] - a[mIndex];
	}
	for (int i = mIndex; i != m; i = (i + 1) % n) {
		b[i]--;
		b[mIndex]++;
		if (b[i] < 0) return false;
	}
	return true;
}
int main() {
	while (~scanf("%d%d", &n, &m)) {
		long long mVal = -1;
		vt.clear();
		m--;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			if (mVal == -1 || mVal >= a[i]) {
				if (mVal > a[i])vt.clear();
				mVal = a[i];
				vt.push_back(i);
			}
		}
		for (int i = 0; i < (int)vt.size(); i++) {
			int mIndex = vt[i];
			if (check(mIndex))break;
		}
		for (int i = 0; i < n; i++) {
			printf("%lld%c", b[i], i == n - 1 ? '\n' : ' ');
		}
	}
}
/*
3 1
6 5 1
*/

local_offer #招聘  #网易  #LCS  #暴力 
navigate_before