[UVA][dfs、剪枝] 10890 - Maze
Problem D
Maze
Input File: d.in
Output: Standard Output
In this problem you are given a square maze of dimension N with N*N blocks. Each block is numbered as follows:
|
N-1, 0 |
N-1, 1 |
… |
… |
N-1, N-1 |
|
… |
… |
… |
… |
… |
|
2, 0 |
2, 1 |
2, 2 |
… |
… |
|
1, 0 |
1, 1 |
1, 2 |
… |
… |
|
0, 0 |
0, 1 |
0, 2 |
… |
0, N-1 |
The maze has only one entry which is at (0, 0) and only one exit which is at (N-1, N-1). From each block you can move in four directions (N, E, W, S) and the cost is 1 for each movement among the maze but collecting treasure does not require any cost.. Some blocks contain treasures that you will have to collect. Suppose there are T treasures in the maze and you have to collect at least S (S ≤ T) treasures from them. In this problem, you are requested to find an optimal way from starting location to ending location and take at least S treasures from the maze. Remember that, you can visit a block more than once if you want.
Input
The first line of the input contains three integers N (N ≤ 30), T (T ≤ 30) and S (S ≤ 10 and S ≤ T) describing the dimension of the maze, number of treasures in the maze and number of treasures that you can take. After that, there are T lines. Each line contains two numbers representing the position of the treasure in the maze. The input may contain multiple test cases and ends with three zeros for N, T and S.
Output
Each test case produces one line of output. This line should contain the output serial no as shown in the sample output and a number representing the minimum cost which is required to collect the treasures.
Sample Input Output for Sample Input
|
2 0 2 1 2 2 0 2 4 4 2 2 0 2 1 2 2 0 2 0 0 0 |
Case 1: 10 Case 2: 6 |
Problem setter: Syed Monowar Hossain
Special Thanks: Derek Kisman
寫 A* 沒過，一直 TLE。我想下一次寫的時候，應該先抓一組近似解，然後再跑 A*。
不然 priority_queue 一直吐不出解。
那這題我最後用了 dfs + 減枝。
其實很簡單的，基本上對於點還是按照順序排序比較好，搜索起來比較可以在較早的時間得到解答。
接著就可以在得到解的時候，快速把不可能的解給剪掉。
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, S, T, X[35], Y[35];
int ret, U[35];
void dfs(int nd, int cost, int used) {
if(cost+(N-X[nd]+N-Y[nd]-2)*1.1 >= ret)
return;
if(used == S) {
ret = min(ret, cost+(N-X[nd]+N-Y[nd]-2));
return;
}
int i;
for(i = 1; i < T; i++) {
if(!U[i]) {
U[i] = 1;
dfs(i, cost+abs(X[i]-X[nd])+abs(Y[i]-Y[nd]), used+1);
U[i] = 0;
}
}
}
int main() {
int i, j, cases = 0;
while(scanf("%d %d %d", &N, &T, &S) == 3) {
if(N+S+T == 0)
break;
int g[35][35] = {};
for(i = 0; i < T; i++) {
scanf("%d %d", &X[i], &Y[i]);
g[X[i]][Y[i]]++;
}
X[0] = 0, Y[0] = 0;
T = 1;
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++)
if(g[i][j])
X[T] = i, Y[T] = j, T++;
U[i] = 0;
}
ret = 0xffffff;
dfs(0, 0, 0);
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}