bzoj3393

题解：

spfa

允许多次进队

代码：

#include<bits/stdc++.h>

using namespace std;

struct que{int x,y,dire,dist;}now,wrk;

bool operator<(const que &a,const que &b){return a.dist>b.dist;}

priority_queue <que> q;

const int mx[]={,,,-},my[]={,,-,};

int n,m,sx,sy,ex,ey,mrk[][],dist[][][];

int main()

{

    scanf("%d%d",&m,&n);

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

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

      {

        char ch=getchar();

        while (ch!='C'&&ch!='.'&&ch!='*')ch=getchar();

        if (ch=='*')mrk[i][j]=;

        if (ch=='C')

         {

             if (!sx){sx=i;sy=j;}

            else {ex=i;ey=j;}

         }

      }

    memset(dist,,sizeof(dist));

    now.x=sx;now.y=sy;now.dist=;

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

     {

        now.dire=i;

        q.push(now);

        dist[sx][sy][i]=;

     }

    while (!q.empty())

     {

        now=q.top();q.pop();

        int k=now.dire;

        wrk=now;

        while (wrk.x+mx[k]>=&&wrk.x+mx[k]<=n&&wrk.y+my[k]>=

        &&wrk.y+my[k]<=m&&!mrk[wrk.x+mx[k]][wrk.y+my[k]]

        &&dist[wrk.x+mx[k]][wrk.y+my[k]][k]>wrk.dist)

         {

            wrk.x+=mx[k];wrk.y+=my[k];

            dist[wrk.x][wrk.y][k]=dist[now.x][now.y][k];

            q.push(wrk);

         }

        wrk=now;wrk.dist++;

        for (int k=;k<;k++)

        if(dist[now.x][now.y][k]>now.dist+)

         {

            dist[now.x][now.y][k]=now.dist+;

            wrk.dire=k;

            q.push(wrk);

         }

     }

    int ans=1e9;

    for (int k=;k<;k++)

      ans=min(ans,dist[ex][ey][k]);

    printf("%d\n",ans);

}