首页 > ACM题库 > HDU-杭电 > HDU 3036- Escape[解题报告]HOJ
2014
02-27

HDU 3036- Escape[解题报告]HOJ

Escape

问题描述 :

R’s girl friend D is on military training somewhere near Harbin. She feels bad every day and night. She complains about every terrible thing to R. And sometimes she would wail loudly that she had hurt her foot.

R has a motto, which is "Finding her is my lifetime fate, yet cherishing her is my daily job." So he made a plan, which called "Prison Break", as you know, the same with the famouse American play.

R found out that there were several holes on the wire netting which surrounds the military camp. Or maybe, just R did that. Whatever, R told this to his girl friend D. D gathered the girl comrades, and they decided to escape this night. To help to make the escape safe, R investigated the camp again. And something worse found was soldiers walked guard even in the night. But the good news was they drunk much every night and they were dozing off every night.

The girls’ escape, will not make no sound. Once they take action, the evil commander will send his soldiers(not the drunk ones of course) to stop them. You can assume that the soldiers will get there after T seconds. So if they take more time than T, they will get caught.

Initially, there is one person on every empty square in the camp and these persons should move to a hole on the wire netting to exit. They can move one square per second to the North, South, East or West. While escaping, multiple persons can be on a single square. The holes are narrow, however, and only one person can leave through a hole per second.

Now, R and D wants to know whether this action will be successful.If successful, then how much time it will take to get out from the camp.

输入:

Multiple cases.
Each test case has the following format:

One line with three integers r, c and T , separated by a single space, satisfying 3 <= r, c <= 12: the size of the camp

Then r lines with c characters descripes the camp.

Girls represented by a ‘.’ . Drunk soldiers and the wire netting represented by an ‘X’, you can assume that the drunk ones will not move even one square. And the hole is ‘E’, meaning an exit to the girls.

Input file ends with EOF.

输出:

Multiple cases.
Each test case has the following format:

One line with three integers r, c and T , separated by a single space, satisfying 3 <= r, c <= 12: the size of the camp

Then r lines with c characters descripes the camp.

Girls represented by a ‘.’ . Drunk soldiers and the wire netting represented by an ‘X’, you can assume that the drunk ones will not move even one square. And the hole is ‘E’, meaning an exit to the girls.

Input file ends with EOF.

样例输入:

5 5 3
XXEXX
X...X
E...X
X...E
XXXXX

样例输出:

3

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;

typedef long long LL;

const double EPS = 1e-8;

struct snode
{
	int r, c, d;
	snode() {}
	snode(int rr, int cc, int dd): r(rr), c(cc), d(dd) {}
};

int dr[4] = {-1, 0, 1, 0}; 
int dc[4] = {0, -1, 0, 1};
int R, C, T,cntg, cnte;
char g[20][20];
int ex[20][20], gl[20][20];
int dis[200][200];

void bfs(int sr, int sc)
{
	int r, c, d, nr, nc, sn=ex[sr][sc], tn;
	char vis[20][20];
	memset(vis, 0, sizeof(vis));
	queue<snode> q;
	q.push(snode(sr, sc, 0));
	vis[sr][sc] = 1;
	while (!q.empty())
	{
		r = q.front().r; c = q.front().c; d = q.front().d;
		q.pop();
		for (int i = 0; i < 4; ++i)
		{
			nr = r+dr[i]; nc = c+dc[i];
			if (nr<0||nc<0||nr>=R||nc>=C) continue;
			if (g[nr][nc]=='X' || g[nr][nc]=='E') continue;
			if (vis[nr][nc]) continue;
			vis[nr][nc] = 1;
			if (g[nr][nc]=='.')
			{
				tn = gl[nr][nc];
				dis[tn][sn] = d+1;
			}
			q.push(snode(nr, nc, d+1));
		}
	}
}

struct smatch
{
	int N, M, ans;
	vector<int> adj[200];
	int match[20000];
	char vis[20000];
	inline void init(int _N, int _M)
	{
		memset(match, 0, sizeof(match));
		N = _N; M = _M;
		for (int u = 1; u <= N; ++u)
			adj[u].clear();
	}
	inline void addedge(int u, int v)
	{adj[u].push_back(v);}
	bool dfs(int u)
	{
		int i, v;
		for (i = 0; i < adj[u].size(); ++i)
		{
			v = adj[u][i];
			if (vis[v]) continue;
			vis[v] = 1;
			if (!match[v] || dfs(match[v]))
			{
				match[v] = u;
				return 1;
			}
		}
		return 0;
	}
	int hgr()
	{
		int res = 0;
		for (int u = 1; u <= N; ++u)
		{
			memset(vis, 0, sizeof(vis));
			if (dfs(u)) ++res;
		}
		return ans = res;
	}
}homura;

bool ok(int t)
{
	int i, j, k;
	homura.init(cntg, cnte*t);
	for (i = 1; i <= cntg; ++i)
		for (j = 1; j <= cnte; ++j)
			for (k = dis[i][j]; k <= t; ++k)
				homura.addedge(i, (j-1)*t+k);
	homura.hgr();
	if (homura.ans>=cntg) return 1;
	else return 0;
}

int solve()
{
	int i, j, k, r, c, mind;
	if (cntg==0) return 0;
	for (int i = 1; i <= cntg; ++i)
	{
		mind = 9999;
		for (int j = 1; j <= cnte; ++j)
			mind = min(mind, dis[i][j]);
		if (mind==9999) return 9999;
	}
	int low = 1, high = 256, mid;
	while (low < high)
	{
		mid = (low+high)>>1;
		if (ok(mid)) high = mid;
		else low = mid+1;
	}
	return low;
}

int main()
{
	int i, j, k, r, c;
	while (~scanf("%d%d%d", &R, &C, &T))
	{
		getchar();
		for (r = 0; r < R; ++r)
			scanf("%s", g[r]);
		memset(dis, 0x3f, sizeof(dis));
		memset(ex, 0, sizeof(ex));
		memset(gl, 0, sizeof(gl));
		cntg = cnte = 0;
		for (r = 0; r < R; ++r)
			for (c = 0; c < C; ++c)
			{
				if (g[r][c]=='E') ex[r][c] = ++cnte;
				if (g[r][c]=='.') gl[r][c] = ++cntg;
			}
		for (r = 0; r < R; ++r)
			for (c = 0; c < C; ++c)
				if (g[r][c]=='E') bfs(r, c);
		int ans = solve();
		if (ans > T) puts("impossible");
		else printf("%d\n", ans);
	}
	return 0;
}

  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的