BombMan.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <sstream>
#include <set>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <time.h>
#include <queue>
using namespace std;
#define SIZEOFARRAY(s) sizeof(s)/sizeof(s[0])
#define MAXELEMENTS 50
/* https://www.topcoder.com/stat?c=problem_statement&pm=2274&rd=5009 */
	
struct node
{
	size_t x;
	size_t y;
	size_t steps;
	size_t bombs;
	node() : x(0), y(0), steps(0), bombs(0) {}
	node (size_t xx, int yy, size_t w, size_t s) : x(xx), y(yy), steps(w), bombs(s) {}

	bool operator<(const node &rhs) const
	{
		return this->steps > rhs.steps;
	}
};

class BombMan
{
	bool visited[MAXELEMENTS][MAXELEMENTS];
	priority_queue<node> pq;
	node getStart(vector<string> board);
public:
	int shortestPath(vector<string> maze, int bombs);
};

node BombMan::getStart(vector<string> maze)
{
	queue< pair<int, int> > bfs;
	size_t height = maze.size();
	size_t width = maze[0].length();

	memset(visited, 0, sizeof(visited));
	node start;
	bfs.push(make_pair(0, 0));
	visited[0][0] = true;
	bool foundA = false;

	while (!bfs.empty()) {
		pair<int, int> n = bfs.front();
		bfs.pop();
		if (n.first >= 0 && n.first < height
			&& n.second >= 0 && n.second < width)
		{
			if (maze[n.first][n.second] == 'B')
			{
				start.x = n.first;
				start.y = n.second;
				foundA = true;
				break;
			}

			pair<int, int> right = make_pair(n.first + 1, n.second);
			pair<int, int> down = make_pair(n.first, n.second + 1);

			if (!visited[right.first][right.second])
			{
				bfs.push(right);
				visited[right.first][right.second] = true;
			}
			if (!visited[down.first][down.second])
			{
				bfs.push(down);
				visited[down.first][down.second] = true;
			}
		}
	}
	assert(foundA);
	return start;
}

int BombMan::shortestPath(vector<string> maze, int bombs)
{
	size_t height = maze.size();
	size_t width = maze[0].length();
	node start = getStart(maze);

	start.bombs = bombs;
	pq.push(start);
	memset(visited, 0, sizeof(visited));

	int dX[] = {1,0,-1,0}, dY[] = {0,1,0,-1};

	while (!pq.empty())
	{
		node top = pq.top();
		pq.pop();
		if (maze[top.x][top.y] == 'E')
			return top.steps;

		if (visited[top.x][top.y]) continue;

		visited[top.x][top.y] = true;
		for (size_t x = 0; x < 4; ++x)
		{
			int dx = top.x + dX[x];
			int dy = top.y + dY[x];
			if (dx >= 0 && dx < height
				&& dy >= 0 && dy < width && (dx != top.x || dy != top.y))
			{
				if (maze[dx][dy] == '#' && top.bombs > 0)
				{
					pq.push(node(dx, dy, top.steps + 3, top.bombs - 1));
				}
				else if (maze[dx][dy] != '#')
				{
					pq.push(node(dx, dy, top.steps + 1, top.bombs));
				}
			}
		}
	}

	return -1;
}

void TEST(vector<string> maze, int bombs, int expected)
{
	clock_t start, end;
	double cpu_time_used;

	start = clock();
	BombMan bombMan;

	int result = bombMan.shortestPath(maze, bombs);
	
	assert( result == expected );

	end = clock();
	cpu_time_used = ((double) (end - start));
	cout<<"Time taken : "<<cpu_time_used<<endl;
}

vector< vector<int> > convert(string *list, int n)
{
	vector< vector<int> > ret(n, vector<int> (n));

	for (int i = 0; i< n; ++i)
	{
		string str = list[i];

		for (int j = 0, len = str.length(); j < len; ++j) {
			istringstream iss(str.substr(j,1));

			iss >> ret[i][j];
		}
	}

	return ret;
}

template <class T>
vector<T> convertEx(T *list, int n)
{
	vector<T> ret;

	for (int i = 0; i< n; ++i)
	{
		ret.push_back(list[i]);
	}

	return ret;
}

void Test1()
{
	string maze[]= {".....B.",
 ".#####.",
 ".#...#.",
 ".#E#.#.",
 ".###.#.",
 "......."};

	TEST(convertEx(maze, SIZEOFARRAY(maze)), 1, 8);
}

void Test2()
{
	string maze[]= {"B.#.#.#...E"};

	TEST(convertEx(maze, SIZEOFARRAY(maze)), 2, -1);
}

void Test3()
{
	string maze[]= {"..#####",
 "B.#####",
 "..#####",
 "#######",
 "####...",
 "####.E."};

	TEST(convertEx(maze, SIZEOFARRAY(maze)), 4, 17);
}

void Test4()
{
	string maze[]= 	
{".#.#.#.#B#...#.#...#.#...#.#...#.#...#.#.#.......",
 ".#.#.#.#.#.###.###.#.###.#.#.###.###.#.#.#.###.##",
 ".#.#.#...#.#.#.#.#.#...#.....#.#.#...#...#.#.#...",
 ".#.#.###.#.#.#.#.#.###.#.#####.#.###.###.#.#.###.",
 ".............#.#...#...#.....#.#.#...#.#.#.....#.",
 "##.#######.###.#.#####.#.#####.#.###.#.#.#.#.####",
 ".#.#.....#...#...#.#...#...#.#.#...#...#...#.....",
 ".#######.#.#####.#.#.#.#.###.#.###.#.#####.#.####",
 ".#.#.#.#...#.#.#.#.#.#.......#...#.#...#.#.#.....",
 ".#.#.#.###.#.#.#.#.#####.#####.###.###.#.#.######",
 ".....#...#.#...#...#...#...#...#...#.#.#.........",
 "####.###.#.###.###.#.###.#.#.###.###.#.#.########",
 ".......#.........#.#.#.#.#.#.#.#.........#...#...",
 ".#.###.#########.#.#.#.#.###.#.#####.#.#.#.###.##",
 ".#.#.........#.#.#.#.#.....#.#.#.....#.#.........",
 "############.#.#.#.#.#.#####.#.#.################",
 ".#...........#...#.#.#.#...#.#.#...#.#.#.....#...",
 ".#####.#####.###.#.#.#.#.###.#.#.###.#.#.#####.##",
 ".......#...#.#.#.....#...#...#.#.#.#.#...........",
 "##########.#.#.#####.#.###.###.#.#.#.#.##########",
 ".....#...#.....#.#...#.......#.#...#.......#.....",
 "##.#.###.#.###.#.#.#.#.#####.#.#.###.#######.####",
 "...#...#...#.......#.....#.#...#...#.......#.....",
 "####.#.#.#########.#.###.#.#####.###.#.#######.##",
 ".#...#...#.........#.#.....#.........#.#.#.#.....",
 ".#####.#.#.###.#######.#.###.#.#########.#.#.####",
 ".......#.#.#...#.......#.....#.#.#.......#.#.#.#.",
 "########.#.#.#.#####.#.###.#.###.#.#######.#.#.#.",
 ".........#.#.#.#.....#...#.#.........#.#.........",
 "################.#.#.#.#.#.#.#.#######.#.########",
 ".................#.#.#.#.#.#.#...........#.......",
 "########.#####.#.###.#.#.#####.###.#.#####.###.##",
 ".........#...#.#...#.#.#...#.....#.#.........#...",
 ".#####.#####.#.###.#.###.#.#.#.#.#.#####.#.###.#.",
 ".#.....#.........#.#.#...#.#.#.#.#.#.....#...#.#.",
 "####.#####.###.#.#.#.#.#.#.###.###.#.#.#.#.#####.",
 ".....#.....#.#.#.#.#.#.#.#.#...#...#.#.#.#...#...",
 "####.#.#.###.#.#.###.#.###.#.#.#####.#.#.#.######",
 ".....#.#.#.#...#...#.#...#.#.#...#...#.#.#.......",
 "##########.#.#.#.#####.###.#.#.###.#.###.#####.##",
 "...#.#...#...#.#.....#.#...#.#...#.#.#.......#...",
 ".#.#.#.#.#.#.#.#.#.#.###.#.#########.###.#.#.#.#.",
 ".#.#...#...#.#.#.#.#...#.#...#.......#...#.#.#.#.",
 "##.###.#.#.###.#.#.#.#.#####.#.#.#.###.#.########",
 ".......#.#...#.#.#.#.#.#.....#.#.#...#.#.........",
 "####.#######.#.#####.#.###.#.#.###.#.#.#.########",
 "E..#.......#.#.....#.#.#.#.#.#.#...#.#.#.........",
 "##.#.#.#.###.###.###.###.#.#.###.#.#.#.#.#######.",
 ".....#.#...#.#.....#.#.....#...#.#.#.#.#.....#..."};

	TEST(convertEx(maze, SIZEOFARRAY(maze)), 3, 76);

}

void Test5()
{
	string maze[]= {".#..#......#..##.#...#..####......#.#...#.#...#..#", "..#...#..##..##...#.....##..##.#....##..##....#..#", ".#..##..##.......#...#..........##...####......###", "..###.##..#.....##..###...####.#....#..##...#.#...", "###.#.#.#..#........#.....#..#.#.#.#....#..#..#.#.", "#.#.##...####.###...#####.#.#.#..###.......#..##.#", "##.........#.##..##.#.###..##..#.#...#.##....###..", "###.###.#.##...####.##.#.#.###...#..#.###..#.#..##", "...#..#...#.#.###..#...###.#.####.#.###.#...##.#.#", "..........###...#.###.....#.##.##...#.#....#...#.#", "#..#.#.#.##.##.##.....##.###.##.#.##.###...####..#", "..#..#...#....#.##.#.##..##..#...##...#..#######..", "#.#...#.#..#....#..#####..#.##..#..##.#..#####...#", ".........#.###.##.#.##...#...#..##...#....##..#.##", "#...###...#......#.#.###..##..#.#####.####.##...##", "..###.##.#....###..........#.#.##....##..#.###...#", "#..###...##.##..###..#...#######....#.#..#...###..", "#.#####..###...#.##..#.#.#.###......#.###.#.#.#...", "...#..#.###.###..###.##..#.#..##...###..#.#..#..#.", "#.##.#......##...#.#.....##.##.#####..##.##..#.##.", "#.#.#..#.###..#...#...#..#....#...###......##..#..", "##.#.##.#..##..#..###..#..#####...#..###.#.#.#..#.", "#####...#.#...#.#.......##.##.#..#.#.##.#..##...#.", ".#.##.#.##..####..##...........#.###..#####.#.#..#", ".###.#.###.##.#.#..#.###..#..##.#.#.##.......##.#.", "##......#.#.#....###.....B.....##..#.###.#..###...", "#.###...##.####...##..###....#.#.##.#.#####....#.#", "..#####..#...##..........#.#.##...###..#.#...#...#", "..##.#...#.#.#.###...#.#..###.#..#..##.#..###...##", "#...##.....#.#....#....#.###.##.####..#..#.##.....", "#..####...#####.##...#..######.#.#.#..#......###..", "..#.#.#...#....#.......#..##.#.##...#.#.#...#..#.#", "###..##.##...##....#..#....#...#..#............#..", "#.######..###.#..#..#..#..#.#.#.#....####.#....#.#", "..####............#.#.#.####.#...##..##.###....#.#", ".#.#....#..#..###........###..##..#.#.#....##..#..", "..#.......##.##...####.#..###..#....#.#.##.......#", "####.#...#....#.##.#..#.#.##.#...###.##..#.#.#.###", "#..##..###.####..##......#....#.....#...###.###.##", ".#.####..##.#.##.##..#..#...##....##.....####.....", "####....######..#......#..#...##.##..####...###.#.", "#.##..##...##..###.#.#....#......###........#...#.", "##...#.#.#.#.#.....###...#####..#..#.##....#.##..#", ".#....###...#.#..##.##..##..##.#.#.#.##.##..##.#.#", "..########.....#..#...#.#.#.###..#..#.####.###..##", "####..#.#...#..#.####...###...####...##..#.#######", "##...#####.###...#......#.#.......#..##....#..#.##", "...##.##..#...##...#....#.##..#.....##...###..##..", "##...#.#.##..##.##........#..#...#..#..#.....##.#.", "E.##.#.###...#.#####.#.####..#..#..#..###..##.##.."};

	TEST(convertEx(maze, SIZEOFARRAY(maze)), 5, 55);
}

void Test6()
{
	string maze[]= 	{".#.....#.#.#...#.#.", ".###.###.#.#.###.#.", ".......#.#.#.#.....", "######.#.#.#.#.####", "...#.#...#.........", "##.#.###.###.######", ".......#.#...#.....", "######.#.#.###.####", ".#...........#.....", ".#######.#.###.####", ".........#.........", "##.#######.########", "...#.........#.#...", "########.###.#.#.#.", "...........#.....#.", "##########.#.###.#.", "...........#...#.#.", "####.###.#.#.######", ".....#...#.#.......", "####.#.###.###.####", ".....#...#.#.......", "##.#.#.#####.######", "...#.#.#...........", "##B#.#.#.#.###.####", "...#.#.#.#.#.......", ".#.###.#.#.#.###.##", ".#...#.#.#.#...#..E"};

	TEST(convertEx(maze, SIZEOFARRAY(maze)), 0, 49);
}

void Test7()
{
}

int main()
{
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();
	Test6();
	Test7();
	cout<<"success";

	getchar();
	return 0;
}