#include#include#include#include#include#include#include#include#include" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

1301. Cube in Labyrinth

系統 1670 0

http://acm.timus.ru/problem.aspx?space=1&num=1301

一不小心寫了一個三維的spfa? 思路很簡單就是有點繁瑣

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<algorithm>

#include<cmath>

#define LL long long

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;



const int N=15;

const int INF=0x3f3f3f3f;

//typedef pair<int,int>point;

int dist[N][N][N];

bool in[N][N][N];

int stx,sty,ndx,ndy;

struct node

{

    int u[N],d[N],l[N],r[N];

}mem[N][N];

void init(int n,int m)

{

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

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

    {

        mem[i][j].u[0]=4;

        mem[i][j].d[0]=5;

        mem[i][j].l[0]=3;

        mem[i][j].r[0]=2;

        mem[i][j].u[1]=5;

        mem[i][j].d[1]=4;

        mem[i][j].l[1]=2;

        mem[i][j].r[1]=3;

        mem[i][j].u[2]=2;

        mem[i][j].d[2]=2;

        mem[i][j].l[2]=0;

        mem[i][j].r[2]=1;

        mem[i][j].u[3]=3;

        mem[i][j].d[3]=3;

        mem[i][j].l[3]=1;

        mem[i][j].r[3]=0;

        mem[i][j].u[4]=1;

        mem[i][j].d[4]=0;

        mem[i][j].l[4]=4;

        mem[i][j].r[4]=4;

        mem[i][j].u[5]=0;

        mem[i][j].d[5]=1;

        mem[i][j].l[5]=5;

        mem[i][j].r[5]=5;

    }

    cin>>stx>>sty;

    cin>>ndx>>ndy;

    char a,b,c;

    while(cin>>a)

    {

        if(a=='v'||a=='h')

        c=a;

        else

        {

            cin>>b;

            int x,y;

            x=a-'0';

            y=b-'0';

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

            {

                if(c=='v')

                {mem[x][y].d[i]=-1;mem[x+1][y].u[i]=-1;}

                else

                {mem[x][y].r[i]=-1;mem[x][y+1].l[i]=-1;}

            }

        }

    }



}

void solve(int n,int m)

{

    queue<int>qtx,qty,qtk;

    memset(dist,-1,sizeof(dist));

    dist[stx][sty][0]=0;

    in[stx][sty][0]=true;

    qtx.push(stx);

    qty.push(sty);

    qtk.push(0);

    while(!qtx.empty())

    {

        int x=qtx.front();qtx.pop();

        int y=qty.front();qty.pop();

        int k=qtk.front();qtk.pop();

        in[x][y][k]=false;

        if(x-1>=1&&mem[x][y].u[k]!=-1)

        {

            int k1=mem[x][y].u[k];

            if(dist[x-1][y][k1]==-1||dist[x-1][y][k1]>dist[x][y][k]+1)

            {

                dist[x-1][y][k1]=dist[x][y][k]+1;

                if(in[x-1][y][k1]==false)

                {

                    in[x-1][y][k1]=true;

                    qtx.push(x-1);qty.push(y);qtk.push(k1);

                }

            }

        }

        if(x+1<=n&&mem[x][y].d[k]!=-1)

        {

            int k1=mem[x][y].d[k];

            if(dist[x+1][y][k1]==-1||dist[x+1][y][k1]>dist[x][y][k]+1)

            {

                dist[x+1][y][k1]=dist[x][y][k]+1;

                if(in[x+1][y][k1]==false)

                {

                    in[x+1][y][k1]=true;

                    qtx.push(x+1);qty.push(y);qtk.push(k1);

                }

            }

        }

        if(y-1>=1&&mem[x][y].l[k]!=-1)

        {

            int k1=mem[x][y].l[k];

            if(dist[x][y-1][k1]==-1||dist[x][y-1][k1]>dist[x][y][k]+1)

            {

                dist[x][y-1][k1]=dist[x][y][k]+1;

                if(in[x][y-1][k1]==false)

                {

                    in[x][y-1][k1]=true;

                    qtx.push(x);qty.push(y-1);qtk.push(k1);

                }

            }

        }

        if(y+1<=m&&mem[x][y].r[k]!=-1)

        {

            int k1=mem[x][y].r[k];

            if(dist[x][y+1][k1]==-1||dist[x][y+1][k1]>dist[x][y][k]+1)

            {

                dist[x][y+1][k1]=dist[x][y][k]+1;

                if(in[x][y+1][k1]==false)

                {

                    in[x][y+1][k1]=true;

                    qtx.push(x);qty.push(y+1);qtk.push(k1);

                }

            }

        }

    }

}

int main()

{

    //freopen("data.in","r",stdin);

    int n,m;

    while(cin>>n>>m)

    {

        init(n,m);

        solve(n,m);

        if(dist[ndx][ndy][0]==-1)

        cout<<"No solution"<<endl;

        else

        cout<<dist[ndx][ndy][0]<<endl;

    }

}


    

1301. Cube in Labyrinth


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久黄色一级视频 | 亚洲黄色激情视频 | 最新精品国产 | 国产成社区在线视频观看 | 996热这里有精品青青草原 | 手机看片福利永久国产日韩 | 中国精品久久 | 又黄又爽又成人免费视频 | 中文字幕免费在线播放 | 四虎精品影院 | 骚婷婷| 94在线成人免费视频 | 免费精品国产自产拍观看 | 在线免费午夜视频 | 99视频九九精品视频在线观看 | 欧美在线中文 | 精品久久久久久久久中文字幕 | 伊人资源 | 天天操夜夜操美女 | 大学生一级毛片高清版 | 天天透天天狠 | 国产在线美女 | 在线观看一级毛片免费 | 男人私人影院免费看视频 | 91亚洲精品 | 欧美seav在线 | 亚洲国产综合专区在线播一一 | a在线观看免费 | 黄在线免费看 | 色香视频在线 | 久久国产在线视频 | 国产精品久久久久影院色 | 深夜福利剧场 | 欧美亚洲国产色综合 | 久久国产乱子伦精品免费看 | 欧美一级在线看 | 日韩午夜免费视频 | 97av视频在线播放 | 二级毛片在线观看 | 国产在线精彩视频 | 九九视频在线观看视频23 |