[UVA] 10426 - Knights' Nightmare
Problem H
Knights'
Nightmare
Input: standard input
Output: standard output
Time Limit: 5 seconds
The people of the remote country KnightLand are crazy about chess. They play chess whenever they get some free time. They have even divided their land into adjacent equal sized squares just like a chessboard. They like the knight of chess so much that they always go from one place to another following a knight's trail, even if it takes a lot of time and energy. In a minute, a KnightLander can make only one jump from one square to another like a knight.
For the past few years, the people of KnightLand are facing a serious problem. A monster has appeared in one of the squares of KnightLand. When it is awake, it eats anyone who enters its square. The good thing is, the monster doesn't move from one square to another and loves to sleep. If one enters its square while it is sleeping, it wakes up and forgets for a year how to sleep. It is remains sleepy for a minute and cannot do any harm to anyone in this time. It then starts eating anyone it gets in its square. Therefore, the person who makes it awake can escape safely from it. But if one comes to that square later, he dies a terrible death.
In order to solve the problem, the 4 leaders of KnightLand are planning to meet together. They want to find a square that can be reached safely and as quickly as possible from the squares where they line in. To be extra careful, they decided that there should not be more than 1 jump in a minute in the whole KnightLand. Now, they want to find out if it is at all possible to meet at any square, and the minimum time required to get there.
Can you help them?
Input
Input consists of multiple test cases and terminated by an EOF. Each test case consists of 4 lines. The first line contains the string "Set#n", where n is the set number. The second line contains number of rows r and number of columns c of squares in KnightLand's map (where 3 <= r <= 16 and 3 <= c <= 16). The third line contains position of each leader in the map, in terms of row# and column# of each. The fourth line gives the position of the monster. Note that the square at the upper left corner of the map has (row#,column#) = (1,1). You may assume that no leader resides in the same square as the monster.
Output
For each set of input, there should be 2 lines of output. The first line should contain the string "Set#n", where n is the set number. The second line should give the minimum time in minutes needed to reach a square (in format shown below), or the string "Meeting is impossible.", whichever is applicable.
Sample InputSet#15 51 1 1 5 5 1 4 43 3Set#23 31 1 1 2 1 3 2 23 2 Sample Output
Set#1
Minimum time required is 6 minutes.Set#2
Meeting is impossible.
Problem setter: Mustaq Ahmed, University of Waterloo, Canada
“To make a very good problem (To generate a good idea, writing an error free
statement and solution) one needs at least 3/4 days of time. The situation
gets even worse when one is asked to set problem from a particular
field. I hope the non-problem setters will understand it soon.”
題目描述：// 真的不好理解
4 個騎士要匯集到同一個格子上，每個騎士按照騎士走法。
到同一個格子上後，騎士們再討論如何解決這頭怪物。
怪物只會在一格，而一開始怪物呈現睡眠狀態，如果有一個騎士經過，怪物便會清醒，之後誰只要經過怪物的領土就會被殺。
騎士們小心翼翼地，一個時刻只能有一個騎士移動一步。
求最少時刻匯集到一地。
題目解法：
分成兩種有無經過怪物之處討論，之後窮舉每一個匯集地點，再討論最多有一個騎士經過怪物的地盤。
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
void bfs(int dist[20][20], int sx, int sy, int n, int m, int mx, int my) {
queue<int> X, Y;
int tx, ty, i;
dist[sx][sy] = 1;
X.push(sx), Y.push(sy);
while(!X.empty()) {
sx = X.front(), X.pop();
sy = Y.front(), Y.pop();
for(i = 0; i < 8; i++) {
tx = sx + dx[i], ty = sy + dy[i];
if(tx <= 0 || ty <= 0 || tx > n || ty > m)
continue;
if(tx == mx && ty == my)
continue;
if(dist[tx][ty] == 0) {
dist[tx][ty] = dist[sx][sy]+1;
X.push(tx), Y.push(ty);
}
}
}
}
void bfs2(int dist[20][20], int sx, int sy, int n, int m) {
queue<int> X, Y;
int tx, ty, i;
dist[sx][sy] = 1;
X.push(sx), Y.push(sy);
while(!X.empty()) {
sx = X.front(), X.pop();
sy = Y.front(), Y.pop();
for(i = 0; i < 8; i++) {
tx = sx + dx[i], ty = sy + dy[i];
if(tx <= 0 || ty <= 0 || tx > n || ty > m)
continue;
if(dist[tx][ty] == 0) {
dist[tx][ty] = dist[sx][sy]+1;
X.push(tx), Y.push(ty);
}
}
}
}
int ret[4][20][20];
int ret2[4][20][20];
int test(int x, int y) {
int time = 0;
int i;
for(i = 0; i < 4; i++) {
if(ret[i][x][y] == 0) // can't search
return 0xfffffff;
time += ret[i][x][y];
}
int mntime = 0xfffffff;
for(i = 0; i < 4; i++) {
if(ret2[i][x][y] == 0)
continue;
mntime = min(mntime, time - ret[i][x][y] + ret2[i][x][y] - 4); // base 4
}
return mntime;
}
int main() {
char testcase[1024];
while(scanf("%s", testcase) == 1) {
puts(testcase);
int n, m, sx[4], sy[4], mx, my;
int i, j, k;
scanf("%d %d", &n, &m);
for(i = 0; i < 4; i++)
scanf("%d %d", &sx[i], &sy[i]);
scanf("%d %d", &mx, &my);
memset(ret, 0, sizeof(ret));
memset(ret2, 0, sizeof(ret2));
for(i = 0; i < 4; i++) {
bfs(ret[i], sx[i], sy[i], n, m, mx, my);
bfs2(ret2[i], sx[i], sy[i], n, m);
}
int mntime = 0xfffffff;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(i == mx && j == my)
continue;
mntime = min(mntime, test(i, j));
}
}
if(mntime != 0xfffffff)
printf("Minimum time required is %d minutes.\n", mntime);
else
printf("Meeting is impossible.\n");
}
return 0;
}