首页 > 代码库 > UVALive 5966 Blade and Sword -- 搜索(中等题)

UVALive 5966 Blade and Sword -- 搜索(中等题)

题意:给一幅地图,P为起点,D为终点,‘*‘为传送阵,到达传送阵可以传到任意一个其他的传送阵,传到以后可以正常走或者再传回来,问P->D最短步数。

分析:这题一定要细心,分析要到位才能搞定,错一点都WA。有两种思路:

1.走到一个传送点之后,将所有能传到的地方都加入队列,然后清除传送阵向量(vector),因为以后不用再互相传了,对于某个传送阵k,以后从别的点传到k的效果还不如从这个点传到k,所以清空传送阵,又因为其他传送阵可以传回来,此时传送阵向量要把当前传送阵push_back进去,以便其他点传过来,每个传送点设一个标记,flag=0说明这个传送点还没用过,flag=1说明这个传送点是被传过来的,还可以传一次,use[][]数组记录某个传送点被用过没有(即通过它传出去过没有),然后搞即可。

代码:(63ms, 0KB)

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <queue>#define Mod 1000000007using namespace std;#define N 1000017char ss[205][205];bool vis[205][205],use[205][205];int n,m,step;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};struct node{    int x,y,tag;    node(int _x,int _y,int _tag)    {        x = _x;        y = _y;        tag = _tag;    }    node(){}}P,D;vector<node> trans;bool OK(int nx,int ny){    if(nx >= 0 && nx < n && ny >= 0 && ny < m)        return 1;    return 0;}bool bfs(){    queue<node> que;    memset(vis,0,sizeof(vis));    memset(use,0,sizeof(use));    que.push(P);    int i,j,k;    vis[P.x][P.y] = 1;    while(!que.empty())    {        int SIZE = que.size();        while(SIZE--)        {            node tmp = que.front();            que.pop();            int nx = tmp.x;            int ny = tmp.y;            if(nx == D.x && ny == D.y)                return 1;            if(ss[nx][ny] == *)   //tag = 1 : 被传过来的,tag = 0 : 传出去            {                if(tmp.tag == 0 || (tmp.tag==1 && !use[nx][ny]))                {                    for(i=0;i<trans.size();i++)                    {                        int x = trans[i].x;                        int y = trans[i].y;                        if(vis[x][y] || (nx == x && ny == y))                            continue;                        trans[i].tag = 1;                        que.push(trans[i]);                    }                    trans.clear();                    trans.push_back(tmp);  //这个点还可以被传回来                    if(tmp.tag == 1)   //被传过来并且没用过的,现在用过了                        vis[nx][ny] = 1;                    use[nx][ny] = 1;                }                if(tmp.tag == 1)   //被传,用过了,就当做普通点好了  别用else if                {                    for(k=0;k<4;k++)                    {                        int kx = nx + dx[k];                        int ky = ny + dy[k];                        if(!OK(kx,ky) || ss[kx][ky] == # || ss[kx][ky] == * || vis[kx][ky])                            continue;                        vis[kx][ky] = 1;                        que.push(node(kx,ky,0));                    }                    vis[nx][ny] = 1;                }            }            else   //普通点,普通走法            {                for(k=0;k<4;k++)                {                    int kx = nx + dx[k];                    int ky = ny + dy[k];                    if(!OK(kx,ky) || ss[kx][ky] == # || vis[kx][ky])                        continue;                    if(ss[kx][ky] != * )  //如果是‘*‘,则不能确定                        vis[kx][ky] = 1;                    que.push(node(kx,ky,0));                }            }        }        step++;    }    return 0;}int main(){    int t,cs = 1,i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        trans.clear();        for(i=0;i<n;i++)        {            scanf("%s",ss[i]);            for(j=0;j<m;j++)            {                if(ss[i][j] == *)                    trans.push_back(node(i,j,0));                else if(ss[i][j] == P)                    P = node(i,j,0);                else if(ss[i][j] == D)                    D = node(i,j,0);            }        }        step = 0;        if(bfs())            printf("Case %d: %d\n",cs++,step);        else            printf("Case %d: impossible\n",cs++);    }    return 0;}
View Code

 

2.统计传送点的数量,如果只有一个传送点,那么不能经过传送点到达,只能走普通路到终点。否则,先走一遍普通路ans = bfs(),再从P搜一个与他最近的传送点,从D搜一个与它最近的传送点,判断这两个传送点是不是同一个,如果是只能再通过图中另一个传送点作为终中继,此时ans = bfsP()+bfsD()+2,不是同一个那就更好处理了,ans = bfsP+bfsD+1。细节问题看代码吧。

代码:(22ms, 0KB)

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <queue>#define Mod 1000000007using namespace std;#define N 1000017struct node{    int x,y,step;}P,D;int n,m;int cnt1,cnt2;char ss[205][205];int vis[205][205];queue<node> que;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int X1,X2,Y1,Y2;int OK(int nx,int ny){    if(nx >= 0 && nx < n && ny >= 0 && ny < m && ss[nx][ny] == .)        return 1;    return 0;}int bfsPD(){    while(!que.empty())        que.pop();    P.step = 0;    memset(vis,0,sizeof(vis));    que.push(P);    vis[P.x][P.y] = 1;    while(!que.empty())    {        node now = que.front();        que.pop();        int nx = now.x;        int ny = now.y;        int step = now.step;        for(int k=0;k<4;k++)        {            int kx = nx + dx[k];            int ky = ny + dy[k];            if(ss[kx][ky] == D)                return step+1;            if(!OK(kx,ky) || vis[kx][ky])  //不考虑‘*‘                continue;            node tmp;            tmp.x = kx;            tmp.y = ky;            tmp.step = step + 1;            vis[kx][ky] = 1;            que.push(tmp);        }    }    return Mod;}int bfsP()    //从P找‘*‘{    int dis = Mod;    while(!que.empty())        que.pop();    memset(vis,0,sizeof(vis));    P.step = 0;    que.push(P);    vis[P.x][P.y] = 1;    while(!que.empty())    {        node now = que.front();        que.pop();        int nx = now.x;        int ny = now.y;        int step = now.step;        if(step >= dis)            return dis;        for(int k=0;k<4;k++)        {            int kx = nx + dx[k];            int ky = ny + dy[k];            if(ss[kx][ky] == *)            {                X1 = kx;                Y1 = ky;                cnt1++;                dis = step + 1;            }            else if(OK(kx,ky))            {                if(!vis[kx][ky])                {                    node tmp;                    tmp.x = kx;                    tmp.y = ky;                    tmp.step = step+1;                    vis[kx][ky] = 1;                    que.push(tmp);                }            }        }    }    return dis;}int bfsD()    //从D找‘*‘{    int dis = Mod;    while(!que.empty())        que.pop();    memset(vis,0,sizeof(vis));    D.step = 0;    que.push(D);    vis[D.x][D.y] = 1;    while(!que.empty())    {        node now = que.front();        que.pop();        int nx = now.x;        int ny = now.y;        int step = now.step;        if(step >= dis)            return dis;        for(int k=0;k<4;k++)        {            int kx = nx + dx[k];            int ky = ny + dy[k];            if(ss[kx][ky] == *)            {                X2 = kx;                Y2 = ky;                cnt2++;                dis = step + 1;            }            else if(OK(kx,ky))            {                if(!vis[kx][ky])                {                    node tmp;                    tmp.x = kx;                    tmp.y = ky;                    tmp.step = step+1;                    vis[kx][ky] = 1;                    que.push(tmp);                }            }        }    }    return dis;}int main(){    int t,cs = 1,i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        int cnt = 0;        for(i=0;i<n;i++)        {            scanf("%s",ss[i]);            for(j=0;j<m;j++)            {                if(ss[i][j] == P)                    P.x = i,P.y = j;                else if(ss[i][j] == D)                    D.x = i,D.y = j;                else if(ss[i][j] == *)                    cnt++;            }        }        int ans = 0;        cnt1 = cnt2 = 0;        if(cnt <= 1)    //少于等于1个传送点,就只能按普通路走过去            ans = bfsPD();        else        {            int d1,d2;            ans = bfsPD();            d1 = bfsP();            d2 = bfsD();            if(cnt1 == cnt2 && cnt1 == 1)  //周围都只有一个点,通过这两个点中介            {                if(X1 == X2 && Y1 == Y2)  //是同一个点,因为至少还有一个点,所以可以传回来                    ans = min(ans,d1+d2+2);                else                    ans = min(ans,d1+d2+1);            }            else  //有不止一个点,可以用不同点传                ans = min(ans,d1+d2+1);        }        if(ans >= Mod)            printf("Case %d: impossible\n",cs++);        else            printf("Case %d: %d\n",cs++,ans);    }    return 0;}
View Code

 

Written by Whatbeg