nyoj 999

题目思路，处理一下地图，把 D E 能看到的地方标记一下。然后就是暴力广搜一下。标记状态，因为同样在同一个点，但是你刚出发到达那点和找到D之后到达相同的点和找到E之后到达相同的点，这3中状态是不同的。用vis[x][y][3]

来标记状态，标记状态知道这题就AC了。

还有另外的思路就是把它们一个一个搜，S-->D-->E S-->D-->E S-->D,E; 分别广搜，取min即可。

下面是第一种，标记状态的方法。另外一种就不写了。

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<vector>

#include<string>

#include<string.h>

#include<queue>

using namespace std;

typedef long long int LL;

typedef short int sint;

const int INF=~(1<<31);

const int MM=105;

int n,m,times;

sint dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};

char maps[MM][MM];

bool vis[MM][MM][3];

struct node

{

    short int x,y,step,now;

};

bool is_out(sint x,sint y)

{

    if(x>=0&&x<n&&y>=0&&y<m) return true;

    return false;

}

int bfs(int sx,int sy)

{

    node first,second;

    if(maps[sx][sy]=='e') first.now=2;

    else if(maps[sx][sy]=='d') first.now=1;

    else if(maps[sx][sy]=='f') first.now=3;

    else first.now=0;

    queue<node>q;

    first.step=0,first.x=(sint)sx,first.y=(sint)sy;

    q.push(first);

    while(!q.empty())

    {

        first=q.front();

        q.pop();

      //  printf("step=%d x=%d y=%d now=%d\n",(int)first.step,first.x,first.y,first.now);

        if(first.now==3) return first.step;

        if(first.step>times) return -1;

        for(int i=0; i<4; i++)

        {

            sint x=first.x+dir[i][0],y=first.y+dir[i][1];

            if(is_out(x,y)&&vis[x][y][first.now]==0&&maps[x][y]!='X')

            {

                int now=first.now;

                second.now=now;

                vis[x][y][first.now]=true;

                if(maps[x][y]=='f') second.now=3;

                if(maps[x][y]=='d'&&now==2) second.now=3;

                else if(maps[x][y]=='d') second.now=1;

                if(maps[x][y]=='e'&&now==1) second.now=3;

                else if(maps[x][y]=='e') second.now=2;

                if(second.now!=3) vis[x][y][second.now]=true;

                second.step=first.step+1,second.x=x,second.y=y;

                q.push(second);

            }

        }

    }

    return -1;

}

void set_map(int dx,int dy,int ex,int ey)

{

    int x,y;

    for(x=dx+1,y=dy; is_out(x,y)&&maps[x][y]=='.'; x++) maps[x][y]='d';

    for(x=dx-1,y=dy; is_out(x,y)&&maps[x][y]=='.'; x--) maps[x][y]='d';

    for(x=dx,y=dy+1; is_out(x,y)&&maps[x][y]=='.'; y++) maps[x][y]='d';

    for(x=dx,y=dy-1; is_out(x,y)&&maps[x][y]=='.'; y--) maps[x][y]='d';

    for(x=ex+1,y=ey; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); x++)

        if(maps[x][y]=='d') maps[x][y]='f';

        else maps[x][y]='e';

    for(x=ex-1,y=ey; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); x--)

        if(maps[x][y]=='d') maps[x][y]='f';

        else maps[x][y]='e';

    for(x=ex,y=ey+1; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); y++)

        if(maps[x][y]=='d') maps[x][y]='f';

        else maps[x][y]='e';

    for(x=ex,y=ey-1; is_out(x,y)&&(maps[x][y]=='.'||maps[x][y]=='d'); y--)

        if(maps[x][y]=='d') maps[x][y]='f';

        else maps[x][y]='e';

}

void p_m()

{

    int i,j;

    for(i=0;i<n;i++)

    {

        for(j=0;j<m;j++)

            printf("%c",maps[i][j]);

        printf("\n");

    }

}

int main(void)

{

    int cases=0;

    while(cin>>n>>m>>times)

    {

        int i,j,sx,sy,dx,dy,ex,ey;

        memset(maps,0,sizeof(maps));

        memset(vis,0,sizeof(vis));

        for(i=0; i<n; i++)

        {

            cin>>maps[i];

            for(j=0; j<m; j++)

            {

                if(maps[i][j]=='S') maps[i][j]='.',sx=i,sy=j;

                if(maps[i][j]=='D') dx=i,dy=j;

                if(maps[i][j]=='E') ex=i,ey=j;

            }

        }

        set_map(dx,dy,ex,ey);

        maps[dx][dy]='X';

        maps[ex][ey]='X';

        printf("Case %d:\n%d\n",++cases,bfs(sx,sy));

    }

    return 0;

}

巴特西

nyoj 999

最新文章

热门文章