首页 > ACM题库 > HDU-杭电 > HDU 3034-Board Game[解题报告]HOJ
2014
02-27

HDU 3034-Board Game[解题报告]HOJ

Board Game

问题描述 :

Jerry developed a new board game recently. The board consists of N*N grids and M pieces have been randomly put in these grids. The game rules are defined as follows.

1. There is a unique grid defined as exit-grid.

2. In the initial state, no pieces is in exit-grid, and all the pieces are not adjacent to each other(in four directions: up, down, left, right).

3. All the M pieces are marked from 1 to M .

4. Each time you are allowed to move one piece to one of its adjacent blocks, which is counted as one step.

5. When you move the pieces, make sure that all the pieces are not adjacent to each other.

6. When the smallest piece, i.e. its marked number is the smallest on the board, is moved to exit-grid, you can take that piece away from the board. Pieces other than the smallest one are also allowed to move to exit-grid but they cannot be taken away.

7. When all the pieces on the board have been taken away, you win the game.

Tom is a very evil person. Every time Jerry playing the board game, he always says he has a better way to win the game, but he is not willing to tell Jerry. Jerry does not know whether Tom’s words are true or not, so he asks for your help to write a program that can count the number of fewest steps to win the board game.

输入:

To simplify the problem, now we limit 2<=N<=6, 1<=M<=4 and all the initial states are correct.

The first line of the input contains a positive integer T(T <= 200), which indicate the number of test cases.

Then follows T cases of inputs:
- a positive integer N
- a positive integer M
- a N*N matrix of characters to indicate the initial state of the board
If the element in the matrix is ‘o’, it means there is no piece in that grid; otherwise, the element is the marked number of that piece. Note that the element of exit-grid is ‘x’.

输出:

To simplify the problem, now we limit 2<=N<=6, 1<=M<=4 and all the initial states are correct.

The first line of the input contains a positive integer T(T <= 200), which indicate the number of test cases.

Then follows T cases of inputs:
- a positive integer N
- a positive integer M
- a N*N matrix of characters to indicate the initial state of the board
If the element in the matrix is ‘o’, it means there is no piece in that grid; otherwise, the element is the marked number of that piece. Note that the element of exit-grid is ‘x’.

样例输入:

2
3 2
x2o
ooo
oo1

3 3
xo1
o2o
3oo

样例输出:

7
-1

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MaxN 40
#define MaxS 2000010
using namespace std;

int n, m, N, px, st, ed, hs, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int d[MaxS], dist[MaxN], len[MaxN], g[MaxN][4], pN[5];
bool adj[MaxN][MaxN];
char s[MaxN][MaxN];

struct HeapNode {
 int s, f;
 HeapNode(){}
 HeapNode(int s, int f):s(s),f(f){}
}heap[MaxS];

void sink(int p)
{
 HeapNode a = heap[p];
 for (int q = p<<1; q <= hs; p = q, q <<= 1) {
 if (q < hs && heap[q+1].f < heap[q].f) ++q;
 if (heap[q].f >= a.f) break;
 heap[p] = heap[q];
 }
 heap[p] = a;
}

HeapNode del()
{
 HeapNode r = heap[1];
 heap[1] = heap[hs--];
 sink(1);
 return r;
}

void swim(int p)
{
 HeapNode a = heap[p];
 for (int q = p>>1; q && a.f < heap[q].f; p = q, q >>= 1)
 heap[p] = heap[q];
 heap[p] = a;
}

void ins(HeapNode a)
{
 heap[++hs] = a;
 swim(hs);
}

int h(int s)
{
 int ret = 0;
 for (int i = 0; i < m; ++i, s /= N) ret += dist[s%N];
 return ret;
}

int AStar()
{
 memset(d, 0x3f, sizeof(d));
 int p[5];
 hs = 0;
 ins(HeapNode(st, h(st)));
 d[st] = 0;
 while (hs > 0) {
 HeapNode u = del();
 int s = u.s, first;
 for (int i = 0; i < m; ++i, s/=N) p[i] = s%N;
 for (int i = 0; i < m; ++i) if (p[i] != px) {first = i; break;}
 for (int i = first; i < m; ++i)
 for (int j = 0; j < len[p[i]]; ++j) {
 int np = g[p[i]][j];
 bool fail = 0;
 for (int k = first; k < m; ++k) if (k != i && adj[np][p[k]]) {fail = 1;break;}
 if (!fail) {
 int v = u.s+pN[i]*(np-p[i]);
 if (d[u.s] + 1 < d[v]) {
 d[v] = d[u.s] + 1;
 if (v == ed) return d[v];
 ins(HeapNode(v, d[v] + h(v)));
 }
 }
 }
 }
 return -1;
}

int main()
{
 //freopen("test.txt", "r", stdin);
 int T;
 scanf("%d", &T);
 while (T--) {
 scanf("%d%d", &n, &m); N = n*n; st = ed = 0;
 memset(adj, 0, sizeof(adj));
 memset(len, 0, sizeof(len));
 pN[0] = 1; for (int i = 1; i <= m; ++i) pN[i] = pN[i-1] * N;
 for (int i = 0; i < n; ++i) scanf("%s", s[i]);
 for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
 int s1 = i*n+j;
 if (s[i][j] == 'x') px = s1;
 else if (s[i][j] != 'o') st += pN[s[i][j]-'1'] * s1;
 for (int d = 0; d < 4; ++d) {
 int x = i + dx[d], y = j + dy[d], s2 = x*n+y;
 if (x >= 0 && x < n && y >= 0 && y < n) {
 g[s1][len[s1]++] = s2;
 adj[s1][s2] = 1;
 }
 }
 }
 for (int i = 0; i < m; ++i) ed = ed*N + px;
 for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dist[i*n+j] = abs(i-px/n) + abs(j-px%n);
 printf("%d\n", AStar());
 }
 return 0;
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮