BZOJ 1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 (BFS,DP)

Posted by 111qqz on Sunday, April 10, 2016

TOC

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 451  Solved: 226
[Submit][Status][Discuss]

Description

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了'x’。例如下图:

. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

贝茜发现自己恰好在点A处,她想去B处的盐块舔盐。缓慢而且笨拙的动物,比如奶牛,十分讨厌转弯。尽管如此,当然在必要的时候她们还是会转弯的。对于一个给定的牧场,请你计算从A到B最少的转弯次数。开始的时候,贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

Input

第 1行: 一个整数 N 行

2..N + 1: 行 i+1 有 N 个字符 ('.', ‘x’, ‘A’, ‘B’),表示每个点的状态。

Output

行 1: 一个整数,最少的转弯次数。

Sample Input

3
.xA

Bx.

Sample Output

2

思路:bfs.我一开始的错误做法是用优先队列,以转弯数为关键字。

但是实际上错的,因为到达同一个点可能之后到达的方法有更少的转弯数,但是在做bfs的时候,之前访问的节点已经被标记了,所以无法更新成更优的值。

正解是类似dp的做法。需要注意不需要vis数组标记。

用dir[x][y][i]表示从i方向到达x,y的需要转弯数。

初始dir[s.x][s.y][0..3]为0,其余为inf

然后更新的时候如果dir[fx][fy][i]=min(dir[x][y][j]+1) 当i!=j

dir[fx][fy][i]=min(dir[x][y][j]) 当i=j

/* ***********************************************
Author :111qqz
Created Time :2016年04月10日 星期日 17时00分22秒
File Name :code/bzoj/1644.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
char maze[N][N];
int n;
bool vis[N][N];
int dir[N][N][5];
struct node
{
    int x,y;


    bool ok ()
    {
    if (x>=0&&x<n&&y>=0&&y<n&&maze[x][y]!='x') return true;
    return false;
    }

    void look()
    {
    cout<<"x:"<<x<<" y:"<<y<<endl;
    }

}s,e;

void bfs()
{
    queue<node>q;
    q.push(s);

    while (!q.empty())
    {
    node pre = q.front(); q.pop();
//	pre.look();
    for ( int i = 0 ; i < 4 ; i++)
    {
        node nxt;
        nxt.x = pre.x + dx4[i];
        nxt.y = pre.y + dy4[i];
            if (!nxt.ok()) continue; 
        for ( int j = 0 ; j < 4 ; j++)
        {
        bool flag = false;
        if (i==j&&dir[nxt.x][nxt.y][i]>dir[pre.x][pre.y][j])
        {
            dir[nxt.x][nxt.y][i] = dir[pre.x][pre.y][j];
            flag = true;
        }
        if (i!=j&&dir[nxt.x][nxt.y][i]>dir[pre.x][pre.y][j]+1)
        {
            dir[nxt.x][nxt.y][i] = dir[pre.x][pre.y][j] + 1;
            flag = true;
        }
        if (flag)
        {
            q.push(nxt);
        }

        }
    }
    }
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

    scanf("%d",&n);
    for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);

    for ( int i = 0 ; i < n ; i ++)
        for ( int j = 0 ; j < n ; j++)
        {
            if (maze[i][j]=='A')
            {
            s.x = i ;
            s.y = j;
            }
            if (maze[i][j]=='B')
            {
            e.x = i ;
            e.y = j ;
            }
        }

    ms(dir,0x3f);
    for ( int i = 0 ; i < 4 ; i++) dir[s.x][s.y][i] = 0;
    bfs();
//	for ( int i = 0 ; i < 4 ; i++) cout<<dir[e.x][e.y][i]<<endl;
    int ans = inf;
    for ( int i = 0 ; i < 4 ; i++) ans = min(ans,dir[e.x][e.y][i]);
    printf("%d\n",ans);

    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付