URAL 1643. Attack of the Dark Fortress
1. 题目
http://acm.timus.ru/problem.aspx?space=1&num=1643
1643. Attack of the Dark Fortress
Time limit: 1.0 second
Memory limit: 64 MB
Knowing that lich Sandro left to fight the King of Hell, Erathian commanders decided to take advantage of his absence and take over the Dark Fortress. An army of crusaders led by Catherine Ironfist set out from Steadwick. On the same day an army of elven snipers led by Gelu set out from the forests of AvLee. The commanders realize that infantry is vulnerable to liches, and the elven arrows are ineffective against the skeletons, hence the two armies should unite and attack the Fortress simultaneously. As Sandro may return any moment, the Fortress should be attacked as soon as possible. As a court cartographer, you are to calculate the number of days required to implement this plan.Erathia is divided into square regions. Some of them are passable, some of them are not. On one day, each army can move to one of the adjacent (sharing a vertex with a current region) passable regions. Some of the Erathian passable regions have a teleport of one of 26 types inside. A type of a teleport is indicated by a capital Latin letter. If an army is located in a region with a teleport, it can move to any region with a teleport of the same type instantly. When two armies are located in the same region, they unite and then start to move as a single army. No army can attack the Fortress (that is, make a move to the region the Fortress is located in) before the union.Input
The first line contains space-separated integers n and m — dimensions of the map of Erathia (1 ≤ n, m ≤ 100). Then the map itself follows — n lines of m characters each. The meaning of the characters:
‘#’ indicates impassable region.
‘.’ indicates passable region.
‘A’…’Z’ indicates a teleport of type corresponding to that letter.
‘$’ indicates Catherine’s army.
‘!’ indicates Gelu’s army.
‘*’ indicates the Fortress.
It is guaranteed that the characters ‘*’, ‘$’, ‘!’ are encountered exactly once on the whole map.Output
Output a single integer — the number of days that should pass before the united army can attack the Fortress. If the Fortress can’t be attacked, output “Impossible”.Samples
input output
Problem Source: USU Junior Contest, October 2008
2. 思路
巫妖王三多出门去打野，铠煞麟·铁拳和嗝噜两人从分别两个不同的地方出发带队去偷家，地图上有障碍物和传送门：有障碍物的地方不能通过，标记有同样字母的传送门可以瞬间相互传送。为了确保偷家成功，铠煞麟·铁拳和嗝噜两人需要互抱大腿，在到达巫妖王家前，必须汇合在一处。求二人能否在巫妖王回家前偷家成功。
花式BFS。先从铠煞麟的起点开始进行BFS，障碍物是传统项目了，传送门的设定比较新颖，BFS到一个传送门X后，同时把所有传送门X的位置入队即可。由于还有两支队伍需要汇合的要求，BFS不能在搜到终点时立即停止，而是需要访问到所有可以访问的位置（即队列为空）。先从铠煞麟的起点开始BFS，用一个矩阵distCath[i][j] 记录铠煞麟到达位置(i, j)所需的步数；再从嗝噜的起点开始进行BFS，用一个矩阵distGelu[i][j] 记录嗝噜到达位置(i, j)所需的步数。
BFS完成后，遍历与终点相邻的8个位置，对于位置(i, j)，如果distCath[i][j] 和distGelu[i][j] 都有合法值，说明铠煞麟和嗝噜两人可以在此处会师，max(distCath[i][j] , distGelu[i][j] )即为一个候选结果，找出最小的候选结果即可。如果一个候选结果都没有，则判定失败。
3.代码
比较懒，两个BFS直接复制粘贴了。
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
#define MAX_SIZE 100
// #define DEBUG 1
struct PositionRecord;
typedef struct PositionRecord Position;
typedef Position *PtrToPosition;
struct PositionRecord {
int row;
int col;
int time;
};
typedef char Map[MAX_SIZE][MAX_SIZE];
typedef int Distance[MAX_SIZE][MAX_SIZE];
void solveE2f();
void inputMap(Map map, int height, int width);
int getTime(Map map, int height, int width);
void getSpecialPosition(Map map, int height, int width, PtrToPosition posFortress, PtrToPosition posCatherine, PtrToPosition posGelu, vector<Position> teleports[]);
void setPosition(PtrToPosition p, int row, int col);
int getAvailablePosition(Map map, int height, int width, Position pos, PtrToPosition available);
int isAvailable(Map map, int height, int width, int row, int col);
void printMap(Map map, int height, int width);
void printDist(Distance map, int height, int width);
int main() {
solveE2f();
return 0;
}
Map map;
void solveE2f() {
int height, width, time;
scanf("%d %d", &height, &width);
inputMap(map, height, width);
time = getTime(map, height, width);
if (time == -1)
printf("Impossible\n");
else
printf("%d\n", time);
}
void inputMap(Map map, int height, int width) {
int i, j;
char mark;
for (i = 0; i < height; ++i) {
for (j = 0; j < width;) {
scanf("%c", &mark);
if (mark != '\n') {
map[i][j++] = mark;
}
}
}
}
Position queueCath[MAX_SIZE * MAX_SIZE], queueGelu[MAX_SIZE * MAX_SIZE];
Position queue[MAX_SIZE * MAX_SIZE];
Distance distCath, distGelu;
vector<Position> teleports[26];
int getTime(Map map, int height, int width) {
int qCathFront, qCathRear, qGeluFront, qGeluRear;
int front = 0, rear = 0, time = 0, availableNum, i, j, canGoToFortress, candTime;
int offsetRow[8] = { -1, -1, 0, +1, +1, +1, 0, -1 }, offsetCol[8] = { 0, +1, +1, +1, 0, -1, -1, -1 }, fRow, fCol;
Position posFortress, posCath, posGelu, posCurr, posAvailable[8], posNext, posTmp;
for (i = 0; i < height; ++i) {
for (j = 0; j < width; ++j) {
distCath[i][j] = -1;
distGelu[i][j] = -1;
}
}
posCath.time = 0;
posGelu.time = 0;
getSpecialPosition(map, height, width, &posFortress, &posCath, &posGelu, teleports);
queue[rear++] = posCath;
distCath[posCath.row][posCath.col] = 0;
canGoToFortress = 0;
while (front != rear) {
posCurr = queue[front++];
availableNum = getAvailablePosition(map, height, width, posCurr, posAvailable);
for (i = 0; i < availableNum; ++i) {
posNext = posAvailable[i];
posNext.time = posCurr.time + 1;
if (map[posNext.row][posNext.col] == '*') {
canGoToFortress = 1;
if (distCath[posNext.row][posNext.col] == -1)
distCath[posNext.row][posNext.col] = posNext.time;
} else if ((map[posNext.row][posNext.col] == '.' || map[posNext.row][posNext.col] == '!') && distCath[posNext.row][posNext.col] == -1) {
queue[rear++] = posNext;
distCath[posNext.row][posNext.col] = posNext.time;
} else if (map[posNext.row][posNext.col] >= 'A' && map[posNext.row][posNext.col] <= 'Z') {
for (j = 0; j < teleports[map[posNext.row][posNext.col] - 'A'].size(); ++j) {
posTmp = teleports[map[posNext.row][posNext.col] - 'A'].at(j);
if (distCath[posTmp.row][posTmp.col] == -1) {
posTmp.time = posNext.time;
queue[rear++] = posTmp;
distCath[posTmp.row][posTmp.col] = posTmp.time;
} else {
break;
}
}
}
}
}
#ifdef DEBUG
printDist(distCath, height, width);
#endif
if (canGoToFortress == 0) {
return -1;
}
rear = 0;
front = 0;
queue[rear++] = posGelu;
distGelu[posGelu.row][posGelu.col] = 0;
canGoToFortress = 0;
while (front != rear) {
posCurr = queue[front++];
availableNum = getAvailablePosition(map, height, width, posCurr, posAvailable);
for (i = 0; i < availableNum; ++i) {
posNext = posAvailable[i];
posNext.time = posCurr.time + 1;
if (map[posNext.row][posNext.col] == '*') {
canGoToFortress = 1;
if (distGelu[posNext.row][posNext.col] == -1)
distGelu[posNext.row][posNext.col] = posNext.time;
}
else if ((map[posNext.row][posNext.col] == '.' || map[posNext.row][posNext.col] == '$') && distGelu[posNext.row][posNext.col] == -1) {
queue[rear++] = posNext;
distGelu[posNext.row][posNext.col] = posNext.time;
}
else if (map[posNext.row][posNext.col] >= 'A' && map[posNext.row][posNext.col] <= 'Z') {
for (j = 0; j < teleports[map[posNext.row][posNext.col] - 'A'].size(); ++j) {
posTmp = teleports[map[posNext.row][posNext.col] - 'A'].at(j);
if (distGelu[posTmp.row][posTmp.col] == -1) {
posTmp.time = posNext.time;
queue[rear++] = posTmp;
distGelu[posTmp.row][posTmp.col] = posTmp.time;
} else {
break;
}
}
}
}
}
#ifdef DEBUG
printDist(distGelu, height, width);
#endif
if (canGoToFortress == 0) {
return -1;
}
time = MAX_SIZE * MAX_SIZE + 1;
for (i = 0; i < 8; ++i) {
fRow = posFortress.row + offsetRow[i];
fCol = posFortress.col + offsetCol[i];
if (fRow >= 0 && fRow < height && fCol >= 0 && fCol < width) {
if (distCath[fRow][fCol] != -1 && distGelu[fRow][fCol] != -1) {
candTime = distCath[fRow][fCol] > distGelu[fRow][fCol] ? distCath[fRow][fCol] : distGelu[fRow][fCol];
if (time > candTime) {
time = candTime;
}
}
}
}
if (time == MAX_SIZE * MAX_SIZE + 1)
return -1;
else
return time + 1;
}
void getSpecialPosition(Map map, int height, int width, PtrToPosition posFortress, PtrToPosition posCatherine, PtrToPosition posGelu, vector<Position> teleports[]) {
int i, j;
for (i = 0; i < height; ++i) {
for (j = 0; j < width; ++j) {
if (map[i][j] == '*')
setPosition(posFortress, i, j);
else if (map[i][j] == '$')
setPosition(posCatherine, i, j);
else if (map[i][j] == '!')
setPosition(posGelu, i, j);
else if (map[i][j] >= 'A' && map[i][j] <= 'Z') {
PtrToPosition p = (PtrToPosition)malloc(sizeof(Position));
setPosition(p, i, j);
teleports[map[i][j] - 'A'].push_back(*p);
//free(p);
}
}
}
}
int getAvailablePosition(Map map, int height, int width, Position pos, PtrToPosition available) {
int num = 0, row, col, i, offsetRow[8] = {-1, -1, 0, +1, +1, +1, 0, -1}, offsetCol[8] = {0, +1, +1, +1, 0, -1, -1, -1};
for (i = 0; i < 8; ++i) {
row = pos.row + offsetRow[i];
col = pos.col + offsetCol[i];
if (isAvailable(map, height, width, row, col))
setPosition(&available[num++], row, col);
}
return num;
}
int isAvailable(Map map, int height, int width, int row, int col) {
if (row >= 0 && row < height && col >= 0 && col < width && map[row][col] != '#')
return 1;
else
return 0;
}
void setPosition(PtrToPosition p, int row, int col) {
p->row = row;
p->col = col;
}
void printMap(Map map, int height, int width) {
int i, j;
for (i = 0; i < height; ++i) {
for (j = 0; j < width; ++j) {
printf("%c", map[i][j]);
}
printf("\n");
}
}
void printDist(Distance map, int height, int width) {
int i, j;
for (i = 0; i < height; ++i) {
for (j = 0; j < width; ++j) {
printf("%2d ", map[i][j]);
}
printf("\n");
}
printf("\n");
}