[恢]hdu 1035

2011-12-21 10:28:36

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1035

题意：从最上方的第pos列进入，按照迷宫指示走，N向上，D向下，W向左，E向右，输出最终的结果（走出迷宫or循环）。

代码：

# include <stdio.h>
# include <string.h>


char map[110][110] ;
int dp[110][110] ;
int n, m, loop ;


int gao(int x, int y, int step)
{
    if (x < 0 || x >= n || y < 0 || y >= m)
        return -(step-1) ;
    if (dp[x][y] != 0)
    {
        loop = dp[x][y]-1 ;
        return step - dp[x][y] ;
    }
    dp[x][y] = step ;
    
    switch (map[x][y]){
        case 'N': x-- ; break ;
        case 'S': x++ ; break ;
        case 'W': y-- ; break ;
        case 'E': y++ ; break ;
    }
    
    return gao(x, y, step+1) ;
}


int main ()
{
    int pos, ans, i ;
    while (~scanf ("%d %d%*c", &n, &m) && (n||m))
    {
        scanf ("%d%*c", &pos) ;
        for (i = 0 ;i < n ; i++)
            scanf ("%s%*c", map[i]) ;
        memset (dp, 0, sizeof(dp)) ;
        ans = gao(0, pos-1, 1) ;
        if (ans < 0) printf ("%d step(s) to exit\n", -ans) ;
        else printf ("%d step(s) before a loop of %d step(s)\n", loop, ans) ;
    }
    return 0 ;
}