HDOJ 1044

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1044

题意有点类似于红白机上玩过的吃豆子游戏，呵呵。在规定的时间内逃出迷宫，并带走丢在路上的宝石们，价值尽可能的大。

最直接的想法是以宝石为结点，DFS暴力搜索，这样首先需要求俩宝石的最短路径，用A*算法。

然后就TLE了……

然后剪枝吧，比如从A点出发，如d(AC) == d(AB) + d(BC)，那么C点是已经搜索过，continue。并且用了贪心策略，按离当前点的距离远近排序待搜索的结点。

然后继续TLE……

然后反省，是不是我对自己写的A*算法太自信了，应该记录结点间的距离供以后查找。亦或是不是我的整个思路就是错的……

开始不自信了，看解题报告……

原来如此，思路没错，确实应该先纪录结点间的距离。

再次submit，然后WA……

又开始不自信了，难道把A*还是DFS写错了？正当我准备用debug必杀技——print大法时，浏览了一下代码，终于发现问题所在了——const int INF = 1000000，这个INF是用来表示结点间不可达的情况，随手写了个100W，想想应该够大了吧，毕竟迷宫才50*50——再看题目，时间的范围正是100W……一怒之下后面加了俩0，AC了。

早知要纪录所有结点间距离，也不用A*了，BFS更快。

以下代码（因为用了A*，有点长）：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>

using namespace std;

const int INF = 100000000;
const int WALK[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

struct Location
{
    int x_, y_;
};

bool IsLocationEqual(const Location &a, const Location &b)
{
    return a.x_ == b.x_ && a.y_ == b.y_;
}

struct Point
{
    int g_;
    int h_;
    int f_;
};

struct Compare
{
    bool operator ()(const Location &a, const Location &b)
    {
	return (a.x_ > b.x_) ||
	    (a.x_ >= b.x_ && a.y_ > b.y_);
    }
};

typedef map<Location, Point, Compare> PointMap;

struct Jewel
{
    int value_;
    Location loc_;
};

struct Maze
{
    char grids_[50][51];
    int time_;
    Location start_loc_, goal_loc_;
    int jewels_dis_[12][12];
    int cur_index_;
    Jewel jewels_[12];
    int jewels_count_;
    bool exists_[10];
    int wid_, len_;
    int max_value_;

    char Grid(const Location &loc)
    {
	return grids_[loc.y_][loc.x_];
    }

    int GoalIndex()
    {
	return jewels_count_ + 1;
    }

    int StartIndex()
    {
	return jewels_count_;
    } 

    int ThoughtDis(const Location &a, const Location &b)
    {
	return fabs(a.x_ - b.x_) + fabs(a.y_ - b.y_);
    }

    void GetMinFPoint(const PointMap &point_map, Location *p_loc, Point *p_point)
    {
	Point min_point;
	min_point.f_ = INF;
	Location min_loc;
	
	PointMap &temp = const_cast<PointMap &>(point_map);
	PointMap::iterator it;
	for (it=temp.begin(); it!=temp.end(); ++it) {
	    if (it->second.f_ < min_point.f_) {
		min_point = it->second;
		min_loc = it->first;
	    }
	}

	*p_loc = min_loc;
	*p_point = min_point;
    }

    Location NextLocation(const Location &src, const int &index)
    {
	Location r;
	r.x_ = src.x_ + WALK[index][0];
	r.y_ = src.y_ + WALK[index][1];
	return r;
    }

    bool IsLocationLegal(const Location &loc)
    {
	return loc.x_ >= 0 && loc.x_ < wid_ && loc.y_ >= 0 && loc.y_ < len_;
    }

    bool CanMove(const Location &loc)
    {
	return Grid(loc) != '*';
    }

    void RemoveFromTable(PointMap *p_table, const PointMap::iterator &it)
    {
	if (it != p_table->end()) p_table->erase(it->first);
    }

    int MinDis(const Location &start, const Location &goal)
    {
	PointMap open_table, close_table;
	Point start_point;
	start_point.g_ = 0;
	start_point.f_ = start_point.h_ = ThoughtDis(start, goal);
	open_table[start] = start_point;

	while (!open_table.empty()) {
	    Point wait_point;
	    Location wait_loc;
	    GetMinFPoint(open_table, &wait_loc, &wait_point);
	    if (IsLocationEqual(wait_loc, goal)) return wait_point.g_;
	    open_table.erase(wait_loc);
	    close_table[wait_loc] = wait_point;
	    
	    for (int i=0; i<4; ++i) {
		Location next = NextLocation(wait_loc, i);
		if (!IsLocationLegal(next) || !CanMove(next)) continue;
		Point next_point;
		next_point.g_ = wait_point.g_ + 1;
		next_point.h_ = ThoughtDis(next, goal);
		next_point.f_ = next_point.g_ + next_point.h_;
		PointMap::iterator open_it = open_table.find(next);
		if (open_it != open_table.end() &&
			open_it->second.f_ <= next_point.f_) continue;
		PointMap::iterator close_it = close_table.find(next);
		if (close_it != close_table.end() &&
			close_it->second.f_ <= next_point.f_) continue;
		RemoveFromTable(&open_table, open_it);
		RemoveFromTable(&close_table, close_it);
		open_table[next] = next_point;
	    }
	}

	return INF;
    }

    void GenerateAllDis()
    {
	for (int i=0; i<12; ++i) {
	    memset(jewels_dis_[i], -1, 12 * sizeof(jewels_dis_[i][0]));
	}
	for (int i=0; i<jewels_count_+1; ++i) {
	    for (int j=i+1; j<jewels_count_+2; ++j) {
		int t = MinDis(jewels_[i].loc_, jewels_[j].loc_);
		jewels_dis_[i][j] = jewels_dis_[j][i] = t;
	    }
	}
    }

    void GetWaitingIndexes(vector<int> *p_jewel_indexes)
    {
	for (int i=0; i<jewels_count_; ++i) {
	    if (exists_[i]) p_jewel_indexes->push_back(i);
	}
    }

    void Sort(vector<int> *p_jewel_indexes)
    {
	int size = p_jewel_indexes->size();

	for (int i=size-1; i>0; --i) {
	    for (int j=0; j<i; ++j) {
		if (jewels_[(*p_jewel_indexes)[j]].value_ <
			jewels_[(*p_jewel_indexes)[j+1]].value_) {
		    
		    int t = (*p_jewel_indexes)[j];
		    (*p_jewel_indexes)[j] = (*p_jewel_indexes)[j+1];
		    (*p_jewel_indexes)[j+1] = t;
		}
	    }
	}
	
	for (int i=size-1; i>0; --i) {
	    for (int j=0; j<i; ++j) {
		if (jewels_dis_[cur_index_][(*p_jewel_indexes)[j]] >
			jewels_dis_[cur_index_][(*p_jewel_indexes)[j+1]]) {

		    int t = (*p_jewel_indexes)[j];
		    (*p_jewel_indexes)[j] = (*p_jewel_indexes)[j+1];
		    (*p_jewel_indexes)[j+1] = t;		    
		}
	    }
	}
    }

    bool JewelReached(const int &index, vector<int> &searched_jewels)
    {
	vector<int>::iterator it;
	for (it=searched_jewels.begin(); it<searched_jewels.end(); ++it) {
	    if (jewels_dis_[cur_index_][index] ==
		    jewels_dis_[cur_index_][*it] +
		    jewels_dis_[*it][index]) return true;
	}

	return false;
    }

    void SearchNode(const int &max_value, const int &value_sum)
    {
    	const int &goal_dis = jewels_dis_[cur_index_][GoalIndex()];
	if (time_ < goal_dis) return;
	int store = cur_index_;
	vector<int> waiting_jewels;
	waiting_jewels.reserve(10);
	vector<int> searched_jewels;
	searched_jewels.reserve(10);
	GetWaitingIndexes(&waiting_jewels);
	Sort(&waiting_jewels);
    	vector<int>::iterator it = waiting_jewels.begin();
	for (it=waiting_jewels.begin(); it<waiting_jewels.end(); ++it) {
	    if (time_ < jewels_dis_[store][*it]) continue;
	    if (JewelReached(*it, searched_jewels)) continue;
	    time_ -= jewels_dis_[*it][store];
	    cur_index_ = *it;
	    exists_[*it] = false;
	    int temp = value_sum + jewels_[*it].value_;
	    SearchNode(max_value, temp);
	    if (max_value_ == max_value) return;
	    time_ += jewels_dis_[*it][store];
	    exists_[*it] = true;
	    cur_index_ = store;
	    searched_jewels.push_back(*it);
	}

	if (value_sum > max_value_) max_value_ = value_sum;
    }

    void Search()
    {
	cur_index_ = StartIndex();
	memset(exists_, true, 10 * sizeof(exists_[0]));
	max_value_ = -1;
	jewels_[StartIndex()].loc_ = start_loc_;
	jewels_[GoalIndex()].loc_ = goal_loc_;

	int max_value = 0;
	for (int i=0; i<jewels_count_; ++i) {
	    max_value += jewels_[i].value_;
	}

	GenerateAllDis();
	SearchNode(max_value, 0);
    }
};

int main()
{
    int case_time;
    scanf("%d", &case_time);
    
    for (int i=1; i<=case_time; ++i) {
	Maze maze;
	scanf("%d%d%d%d", &maze.wid_, &maze.len_, &maze.time_, &maze.jewels_count_);
	
	for (int j=0; j<maze.jewels_count_; ++j) {
	    scanf("%d", &maze.jewels_[j].value_);
	}
	
	getchar();
	for (int j=0; j<maze.len_; ++j) {
	    for (int k=0; k<maze.wid_; ++k) {
		char c = getchar();
		maze.grids_[j][k] = c;
		if (c >= 'A' && c <= 'J') {
		    Location *p_loc = &maze.jewels_[c-'A'].loc_;
		    p_loc->x_ = k;
		    p_loc->y_ = j;
		} else if (c == '@') {
		    maze.start_loc_.x_ = k;
		    maze.start_loc_.y_ = j;
		} else if (c == '<') {
		    maze.goal_loc_.x_ = k;
		    maze.goal_loc_.y_ = j;
		}
	    }
	    getchar();
	}

	maze.Search();
        printf("Case %d:\n", i);
	if (maze.max_value_ >= 0) {
	    printf("The best score is %d.\n", maze.max_value_);
        } else {
	    printf("Impossible\n");
	}
	if (i < case_time) printf("\n");
    }
    
    return 0;
}