★實驗任務
NC一天要去走一個迷宮，迷宮是由一個 R*C的網格表示，迷宮只有一個出口和一個入口，這個大家都知道，迷宮的出口在第一行，出口在最底行，他想知道走出迷宮的最短時間，這是一個很簡單的問題，至于你信不信，反正我是信了，
★資料輸入
輸入第一行包括四個正整數 R，C，ENT,EXIT（2<=R<=200，2<=C<=200），表示 R 行,C列,入口在第ENT列,出口在EXIT列，
接下 2*R-1行，第2*i行有 C-1個數，第j個數表示網格 g[i][j] 與 g[i][j+1] 之間有墻壁，第 2*i+1 行有 C 個數，第 j 個數表示網格 g[i][j] 和 g[i+1][j] 之間有墻壁，‘0＇表示沒有墻壁，‘1’表示兩個位置之間有墻壁，
★資料輸出
如有有路徑走出，則輸出最短的步數，否則輸出“No Way”(沒有引號)，
#include<iostream> #include<queue> using namespace std; bool vis[203][203]; struct node{ int x,y,step; }; int n,m,s,e; int dx[5]={1,-1,0,0}; int dy[5]={0,0,1,-1}; int row[202][202][202]; int col[202][202][202]; int bfs() { queue<node>q; node p; p.x=1;p.y=s;p.step=1; q.push(p); vis[p.x][p.y]=1; while(q.size()) { node top=q.front(); q.pop(); int tx=top.x; int ty=top.y; int ts=top.step; if(tx==n&&ty==e) { return (ts+1); } for(int i=0;i<=1;i++)//列走 { int xx=tx+dx[i]; int yy=ty+dy[i]; int ss=ts+1; if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]==1||col[tx][xx][yy]==1) continue; else { node tmp; tmp.x=xx;tmp.y=yy;tmp.step=ss; q.push(tmp); vis[xx][yy]=1; } } for(int i=2;i<=3;i++)//行走 { int xx=tx+dx[i]; int yy=ty+dy[i]; int ss=ts+1; if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]==1||row[xx][ty][yy]==1) continue; else { node tmp; tmp.x=xx;tmp.y=yy;tmp.step=ss; q.push(tmp); vis[xx][yy]=1; } } } return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>s>>e; int x; for(int i=1;i<=n;i++) { for(int j=1;j<=m-1;j++) { cin>>x;//第i行第j列到第j+1列能不能走 row[i][j][j+1]=row[i][j+1][j]=x; } if(i!=n) for(int j=1;j<=m;j++) { cin>>x;//第i列到第i+1列第j個格子能不能走 col[i][i+1][j]=col[i+1][i][j]=x; } } int k=bfs(); if(k) cout<<k; else cout<<"No Way"； }
成長從現在開始
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/93386.html
標籤：C++
上一篇：字串專題