oj betch与奔驰

Problem 38: bench与奔驰

Time Limit:1 Ms| Memory Limit:128 MB
Difficulty:2

Description

公园里有个人在练开奔驰 - -!，但是总是撞在bench上 (众人曰：狼来了，快跑啊!)
公园里的bench与奔驰都是无敌的，不会被撞坏。
由于开奔驰的人比较"有特点"，总是向上下左右四个方向开，而且只会在撞到椅子之后改变方向(起步时除外) - -!
现在他给你一张地图，上面标明 他的位置 、 公园里的bench的位置 和 他想到达的位置，可能会有冲出地图的可能
请你告诉他最少撞多少下才能到达目的地，并答应事成之后会给你一辆奔驰..............................................的照片

Input

第一行，两个数，分别表示地图的行和列，都不大于50
以下是地图，"."表示地面，"S"表示起点，"E"表示终点,"B"表示bench(什么意思呢？)
保证只有一个终点和一个起点，并不会出现其他字符

Output

第一行，表示他能不能到达目的地。如果能，就输出"Yes"。否则，输出"No"
如果能到达目的地，就在第二行输出最少的撞击次数

Sample Input

测试数据1:
5 5
BBBBB
B...B
BSE.B
B...B
BBBBB

测试数据2:
3 3
S..
...
..E

Sample Output

测试数据1：
Yes
0

测试数据2：
No

Hint

测试数据1：点火后直接向右走
测试数据2：四个方向都会冲出地图

注意：可能冲出地图，或者永远无法到达。
起初打算用bfs，提交之后超时，估计陷入死循环，不该访问的点多次访问。
后来采用dfs,终于过了
感觉这个题与poj的冰壶类似，不过冰壶碰到障碍物，障碍物会消失，也就是说冰壶可以在
暂停的位置向任意一个方向走（可以原路返回），但是这个题障碍物是无敌的，所以每次停下后，
下次只能向其他两个方向前进（不包括当前前进的方向，和反向），因此每次前进都要判断想那个方向，
还有，要把每次转换方向的点标记(标记为X不标记为B，原因是与障碍物区分出来)，以防止陷入死循环，比如
BBBBB
BB..B
B.S.B
BE..B
BBBBB
如果从S出发向下->向右->向上->向左->向下。。。。。，就发生了死循环（如果不标记每个转向点）。
题目说：如果找到就要输出最小转向次数，所以要把所有的可能都找出来，选择最小的，不能找到就退出。

#include <stdio.h>
#include <memory.h>
 
char map[54][54];
char dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
 
int w, h, sx, sy, minstep;
bool flag;
 
void dfs(int x, int y, int d, int step)
{
    int i, nx, ny;
    for (i=0; i<4; ++i)
    {
        if (d == i)
            continue;
        if (d == 0 && i==1)
            continue;
        if (d == 1 && i == 0)
            continue;
        if (d == 2 && i == 3)
            continue;
        if (d == 3 && i == 2)
            continue;
        nx = x + dir[i][0];
        ny = y + dir[i][1];
        if (map[ny][nx] == 1 || map[ny][nx] == 'B')
            continue;
 
        while (map[ny][nx] == '.')
        {
            nx += dir[i][0];
            ny += dir[i][1];
        }
 
        if (map[ny][nx] == 'E')
        {
            flag = true;
            if (minstep > step)
                minstep = step;
            continue;
        }
        if (map[ny][nx] == 1)
            continue;
        if (map[ny][nx] == 'X')
            continue;
        nx -= dir[i][0];
        ny -= dir[i][1];
        map[ny][nx] = 'X';
        dfs(nx, ny, i, step+1);
        map[ny][nx] = '.';
    }
}
 
int main()
{
    scanf("%d %d", &h, &w);
    getchar();
    int i, j;
    memset(map, 1, sizeof(map));
    for (i=1; i<=h; ++i)
    {
        for (j=1; j<=w; ++j)
        {
            scanf("%c", &map[i][j]);
            if (map[i][j] == 'S')
            {
                sx = j;
                sy = i;
                map[i][j] = 'X';
            }
        }
        getchar();
    }
    flag = false;
    minstep = 2000000000;
    dfs(sx, sy, -1, 0);
    if (flag)
        printf("Yes\n%d\n", minstep);
    else
        puts("No");
    return 0;
}