題目描述

描述 農夫John在外面的田野上搭建了一個巨大的用柵欄圍成的迷宮。幸運的是，他在迷宮的邊界上留出了兩段柵欄作為迷宮的出口。更幸運的是，他所建造的迷宮是一個“完美的”迷宮：即你能從迷宮中的任意一點找到一條走出迷宮的路。給定迷宮的寬度W(1<=W<=38)及高度H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面給出的格式表示一個迷宮。然后計算從迷宮中最“糟糕”的那一個點走出迷宮所需的步數(就是從最“糟糕”的一點，走出迷宮的最少步數）。（即使從這一點以最優的方式走向最靠近的出口，它仍然需要最多的步數）當然了，牛們只會水平或垂直地在X或Y軸上移動，他們從來不走對角線。每移動到一個新的方格算作一步（包括移出迷宮的那一步）這是一個W=5,H=3的迷宮：

+-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+

如上圖的例子，柵欄的柱子只出現在奇數行或奇數列。每個迷宮只有兩個出口。

輸入輸出格式

輸入格式：

?

第一行： W和H（用空格隔開）

第二行至第2 * H + 1行： 每行2 * W + 1個字符表示迷宮

?

輸出格式：

?

輸出一個單獨的整數，表示能保證牛從迷宮中任意一點走出迷宮的最小步數。

?

輸入輸出樣例

輸入樣例#1：?
5 3 +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+ 輸出樣例#1：?
9

說明

翻譯來自NOCOW

USACO 2.4

?

剛讀完題，感覺挺簡單啊，不過研究了一下樣例，一臉懵逼，這咋可能？。

經過機房某位 S型 dalao(son)的解讀，哦，so ga si nei，吆西吆西，interisting！！！

再次就借花獻佛了。

關于的理解題意：

為了便于理解，這里稍微修改一下題目。

奇數行的柵欄（就是由‘+’和‘-’號組成）將其看做一層類似膜結構，一層防護膜(沒有厚度)，穿越不占距離。

然后看偶數列，這里需要將偶數列和其兩側的‘-’看做一個整體，亦可以理解為忽略偶數列，只考慮奇數列。

這里拿樣例圖解：

?

結合上圖，對題意理解就沒什么問題了。

解題剖析：

1.讀入含空格矩陣：

想了半天，試了多種輸入方法，最終貌似只有getline(:不會用戳我啊)可以用。

但是在輸入時，需要多輸入一行，并且第一行和第二行會重復，其他沒毛病，最后貌似沒啥大礙。

scanf("%d%d",&w,&h);w=w*2+1;h=h*2+1;for(int i=1;i<=h+1;i++)getline(cin,a[i]);

讀入是這樣的，若有某位dalao明白以上出現的情況，希望討論區不吝賜教。

2.字符矩陣轉換數字矩陣

在這里定義一個int型map數組。

map[i][j]表示走到這個點需要消耗的距離(偶數行為0，奇數行有空地的話消耗為1)

在字符矩陣中[i][j]這個點為柵欄，不能走，將map[i][j]定義為2.

注意前邊說到，輸入字符時會有一行多余，所以在轉換時處理一下。

此部分代碼為：

?

for(int i=2;i<=h+1;i++)for(int j=0;j<w;j++){if(a[i][j]==32){if((i-1)%2==1)map[i-1][j+1]=0;else if((j+1)%2==0)map[i-1][j+1]=1;else map[i-1][j+1]=0;}else map[i-1][j+1]=2;}

?

3.初始化：

ans[i][j]數組記錄走到 i,j這個點到出口的最近距離，柵欄處直接定義為-1。

void initial() {for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)if(map[i][j]==2)ans[i][j]=-1;else ans[i][j]=214748364; }

?

4.找出出口：

這沒啥好說的，四個邊找出口(注意經以上過程出口可能為0，可能為1)。

for(int i=1;i<=w;i++)if(map[1][i]==0||map[1][i]==1)bfs(1,i);for(int i=1;i<=w;i++)if(map[h][i]==0||map[h][i]==1)bfs(h,i);for(int i=1;i<=h;i++)if(map[i][1]==0||map[i][1]==1)bfs(i,1);for(int i=1;i<=h;i++)if(map[i][w]==0||map[i][w]==1)bfs(i,w);

5.大搜索

已經處理處每一格的消耗距離，在搜索時，加上就好啦。

兩個出口，需要搜索兩邊所以搜完注意初始化，bool型數組。

bool vis[N][M]; struct ahah{int x,y; }str,cur; queue <ahah> que; void bfs(int x,int y) {ans[x][y]=0;vis[x][y]=1;str.x=x;str.y=y;que.push(str);while(!que.empty()){cur=que.front();que.pop() ;for(int i=0;i<4;i++){str.x=cur.x+dx[i];str.y=cur.y+dy[i];if(map[str.x][str.y]!=2&&str.x>=1&&str.x<=h&&str.y>=1&&str.y<=w&&!vis[str.x][str.y]){ans[str.x][str.y]=min(ans[cur.x][cur.y]+map[str.x][str.y],ans[str.x][str.y]);vis[str.x][str.y]=1;que.push(str); }}} memset(vis,0,sizeof(vis)); }

6.找出最大值

將ans數組循環一遍，找出最大值，輸出即可。

完整代碼：

/*......................... 作者：Manjusaka 時間：2018/7/11 題目：P1519 Overfencing ..........................*/#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; #define N int(100) #define M int(210) int dx[5]={0,0,1,-1},dy[5]={1,-1,0,0}; string a[N]; int w,h,MAX; int x[4],y[4],k; int map[N][M]; int ans[N][M]; void check(); void _scanf(); void initial(); void bfs(int ,int ); void _scanf() {scanf("%d%d",&w,&h);w=w*2+1;h=h*2+1;for(int i=1;i<=h+1;i++)getline(cin,a[i]);for(int i=2;i<=h+1;i++)for(int j=0;j<w;j++){if(a[i][j]==32){if((i-1)%2==1)map[i-1][j+1]=0;else if((j+1)%2==0)map[i-1][j+1]=1;else map[i-1][j+1]=0;}else map[i-1][j+1]=2;} // cout<<"\n";for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cout<<map[i][j];}cout<<endl;} check(); } void check() {initial(); for(int i=1;i<=w;i++)if(map[1][i]==0||map[1][i]==1)bfs(1,i);for(int i=1;i<=w;i++)if(map[h][i]==0||map[h][i]==1)bfs(h,i);for(int i=1;i<=h;i++)if(map[i][1]==0||map[i][1]==1)bfs(i,1);for(int i=1;i<=h;i++)if(map[i][w]==0||map[i][w]==1)bfs(i,w);for(int i=1;i<=h;i++){cout<<"\n";for(int j=1;j<=w;j++){printf("%3d",ans[i][j]);}} } void initial() {for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)if(map[i][j]==2)ans[i][j]=-1;else ans[i][j]=214748364; } bool vis[N][M]; struct ahah{int x,y; }str,cur; queue <ahah> que; void bfs(int x,int y) {ans[x][y]=0;vis[x][y]=1;str.x=x;str.y=y;que.push(str);while(!que.empty()){cur=que.front();que.pop() ;for(int i=0;i<4;i++){str.x=cur.x+dx[i];str.y=cur.y+dy[i];if(map[str.x][str.y]!=2&&str.x>=1&&str.x<=h&&str.y>=1&&str.y<=w&&!vis[str.x][str.y]){ans[str.x][str.y]=min(ans[cur.x][cur.y]+map[str.x][str.y],ans[str.x][str.y]);vis[str.x][str.y]=1;que.push(str); }}} memset(vis,0,sizeof(vis)); } void _printf() {for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)MAX=max(MAX,ans[i][j]);printf("\n%d",MAX); } int main() {_scanf();_printf(); }

求助大佬！！：

按題目要求來說二位數組開到100*200應該完全可以啊，為什么會比RE，求解釋。

?

轉載于:https://www.cnblogs.com/rmy020718/p/9297006.html

總結

以上是生活随笔為你收集整理的luogu P1519 穿越栅栏 Overfencing的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。