posts - 7, comments - 2, trackbacks - 0, articles - 1
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

HDOJ 1813 Escape from Tetris

Posted on 2009-03-13 17:55 Lemon 阅读(293) 评论(1)  编辑 收藏 引用

http://acm.hdu.edu.cn/showproblem.php?pid=1813
IDA* g(x,y) = depth, h(x, y) = 从x,y到出口的最小距离,先BFS求每一格到出口的最短距离,剪枝的效果蛮不错的
大家如果能把我的数据跑进200MS应该没问题了

#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= {01-10100-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, 
0sizeof(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
*/

Feedback

# re: HDOJ 1813 Escape from Tetris  回复  更多评论   

2011-10-17 19:22 by xx
秒杀你的数据还是TLE。。。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理