杭电OJ 1044（C++）_c++ oj p1044

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct node
{
	int x;	int y;	int time;
	node(int a, int b, int c) :x(a), y(b), time(c){}
};
 
int W, H, L, M, ans, vals;
char maze[55][55]; //输入的迷宫矩阵
bool vis[55][55]; //迷宫的访问矩阵
int graph[15][15]; //距离虚图
int jewel[15]; //起点、终点、珠宝点的价值
bool isUsed[15]; //起点、终点、珠宝店的访问数组
int dx[4] = { 0, 1, 0, -1 }; //上下方向
int dy[4] = { -1, 0, 1, 0 }; //左右方向
 
//广度优先搜索，建立一张虚图，起点、终点、珠宝点两两之间距离的图
void bfs(int x1, int y1)
{
	memset(vis, false, sizeof(vis));
	int u, v; //u为当前点的索引，v为下一个点的索引
	char a = maze[x1][y1]; //取出当前字符
	if (a == '@')   u = 0; //当前点为起点
	if (a >= 'A' && a <= 'J')  u = a - 'A' + 1; //当前点为珠宝点
	node pos(0, 0, 0), nextpos(0, 0, 0); //当前点，下一步的点
	pos.x = x1;	pos.y = y1;	pos.time = 0;
	queue<node> Q;
	Q.push(pos);
	vis[pos.x][pos.y] = true;
	while (!Q.empty())
	{
		pos = Q.front();	Q.pop();
		if (pos.time == L) //超时，剪枝
			break;
		for (int i = 0; i < 4; i++)
		{
			nextpos.x = pos.x + dx[i];  
			nextpos.y = pos.y + dy[i];  
			nextpos.time = pos.time + 1;
			// 如果为墙壁或者访问过，跳过 
			if (maze[nextpos.x][nextpos.y] == '*' || vis[nextpos.x][nextpos.y]) 
				continue;
			//如果超出矩阵的范围，跳过 
			if (nextpos.x < 0 || nextpos.x >= H || nextpos.y < 0 || nextpos.y >= W) 
				continue;
			vis[nextpos.x][nextpos.y] = true; //设置为访问过
			if (maze[nextpos.x][nextpos.y] == '@') //下一点为起点 
				graph[u][0] = graph[0][u] = nextpos.time;
			else if (maze[nextpos.x][nextpos.y] == '<') //下一点为终点 
				graph[u][M + 1] = graph[M + 1][u] = nextpos.time;
			else if (maze[nextpos.x][nextpos.y] >= 'A'&&maze[nextpos.x][nextpos.y] <= 'J')
			{ //下一点为珠宝点 
				v = maze[nextpos.x][nextpos.y] - 'A' + 1; //取得珠宝顺序的索引
				graph[u][v] = graph[v][u] = nextpos.time;
			}
			Q.push(nextpos); //加入队列 
		}
	}
}
 
//对虚图进行深度优先搜索
void dfs(int index, int limit, int je)
{ //index当前点的索引，limit为当前走过的时间，je为当前取得珠宝的价值和
	if (limit > L) return; //超过时间范围，结束，ans为初始值-1
	if (ans == vals) return; //没超过时间范围的前提下，已取得所有珠宝的总价值
	if (index == M + 1) //到达出口
	{
		if (je > ans)
			ans = je;
		return;
	}
	for (int i = 1; i <= M + 1; i++) //深度优先搜索
	{
		if (isUsed[i] || graph[index][i] == 0) continue; //访问过，或者无法到达
		isUsed[i] = true;
		dfs(i, limit + graph[index][i], je + jewel[i]);
		isUsed[i] = false; //回溯 
	}
}
 
int main()
{
	int t;
	cin >> t;
	for (int tt = 1; tt <= t; tt++)
	{
		ans = -1; //最后结果
		vals = 0; //珠宝价值和
		cin >> W >> H >> L >> M;
		for (int i = 1; i <= M; i++)
		{
			cin >> jewel[i]; //输入珠宝价值
			vals += jewel[i]; //珠宝的价值和
		}
		jewel[0] = jewel[M + 1] = 0; //初始化起点和终点的价值为0
		for (int i = 0; i < H; i++)
			cin >> maze[i]; //输入迷宫数组（一次一行）
		memset(graph, 0, sizeof(graph)); //初始化虚图，无法到达时间距离为0 
		for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
		{ //只允许起点和珠宝点进行广度优先搜索
			if (maze[i][j] == '@' || (maze[i][j] >= 'A'&&maze[i][j] <= 'J'))
				bfs(i, j); //建立起点、终点、珠宝点两两之间距离的虚图   
		}
 
		memset(isUsed, false, sizeof(isUsed));
		isUsed[0] = true;
		dfs(0, 0, 0);
		cout << "Case " << tt << ":" << endl;
		if (ans == -1)
			cout << "Impossible" << endl;
		else
			cout << "The best score is " << ans << "." << endl;
		if (tt != t)
			cout << endl;
	}
	return 0;
}