|
|
Posted on 2009-03-13 17:52 Lemon 阅读(82) 评论(0) 编辑 收藏 引用
http://acm.hdu.edu.cn/showproblem.php?pid=1813IDA* g(x,y) = depth, h(x, y) = 从x,y到出口的最小距离,先BFS求每一个到出口的最短距离,剪枝的效果蛮不错的
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define min(x,y) ((x) > (y)) ? (y) : (x)
char map[20][20];
int limit;
int ans[100];
  int dir[4][2] =  {0, 1, -1, 0, 1, 0, 0, -1};
int n, size;
int mincost[20][20];
char hash[20][20];
typedef struct Node
{
 int x, y;
int time;
 }Node;
Node queue[10000];
int DFS(int depth, int *x, int *y)
{
int flag = 1;
int i, j;
int X[100], Y[100];
for (i = 0; i < size; i++)
  {
if (depth + mincost[x[i]][y[i]] > limit) return 0;
if (mincost[x[i]][y[i]] != 0) flag = 0;
 }
if (flag) return 1;
if (depth == limit) return 0;
for (i = 0; i < 4; i++)
{
ans[depth] = i;
for (j = 0; j < size; j++)
{
X[j] = x[j];
Y[j] = y[j];
if (x[j] == 0 || x[j] == n - 1 || y[j] == 0 || y[j] == n - 1)
continue;
if (map[x[j] + dir[i][0]][y[j] + dir[i][1]] == '0')
{
X[j] += dir[i][0];
Y[j] += dir[i][1];
}
}
if (DFS(depth + 1, X, Y)) return 1;
}
return 0;
}
int main(void)
{
int x[100], y[100];
int i, j, base, top, k, c = 0;
//freopen("1813.txt", "r", stdin);
while (scanf("%d", &n) != EOF)
{
if (c++ != 0) puts("");
long start = clock();
for (i = 0; i < n; i++)
{
scanf("%s", map[i]);
}
size = 0;
for (i = 1; i < n - 1; i++)
{
for (j = 1; j < n - 1; j++)
{
if (map[i][j] == '0')
{
x[size] = i;
y[size] = j;
size++;
}
}
}
if (size == 0)
{
//puts("");
continue;
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (map[i][j] == '1') continue;
base = top = 0;
memset(hash, 0, sizeof(hash));
queue[top].x = i;
queue[top].y = j;
queue[top].time = 0;
hash[i][j] = 1;
top++;
while (base != top)
{
if (queue[base].x == 0 || queue[base].x == n - 1 ||
queue[base].y == 0 || queue[base].y == n - 1)
{
mincost[i][j] = queue[base].time;
break;
}
for (k = 0; k < 4; k++)
{
queue[top].x = queue[base].x + dir[k][0];
queue[top].y = queue[base].y + dir[k][1];
if (map[queue[top].x][queue[top].y] == '0' && !hash[queue[top].x][queue[top].y])
{
hash[queue[top].x][queue[top].y] = 1;
queue[top].time = queue[base].time + 1;
top++;
}
}
base++;
}
}
}
for (limit = 1; ; limit++)
{
if (DFS(0, x, y))
{
for (i = 0; i < limit; i++)
{
if (ans[i] == 0) puts("east");
else if (ans[i] == 1) puts("north");
else if (ans[i] == 2) puts("south");
else puts("west");
}
break;
}
}
//printf("%ld MS\n", clock() - start);
}
return 0;
}
/**//*
4
1101
0001
1100
1001
8
11001010
00000100
10000011
10001110
10001000
10000000
00000000
00000000
8
11001000
00000100
10100000
10000100
10000000
10110000
00000000
00000000
8
11001000
00000100
10100000
10010100
10001000
10110000
00000100
00100100
6
011111
010001
010101
010101
000101
111101
8
11111111
11111111
11111111
11111111
00001111
11111111
11111111
11111111
*/
|