题解：洛谷 P2199 最后的迷宫

题目https://www.luogu.com.cn/problem/P2199

显然，数据最大 $16384\times 16384$ ，数组我们开不下，动态开数组。

对于每一个查询，从起点开始，走一步判断是否能看到火焰杯。

如果已经没法走了，直接拆墙，输出 Poor Harry。

实现

#include<bits/stdc++.h>
using namespace std;
int n,m,Bx,By,Ex,Ey,xux[8][3]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}},xyx[5][3]={{-1,0},{1,0},{0,1},{0,-1}};
vector<char>a[16385];
bool check(int dx,int dy){for(int i=0;i<8;i++){int af=dx,bt=dy;while(true){if(af<1||bt<1||af>n||bt>m||a[af][bt]=='X'){break;}if(af==Ex&&bt==Ey){return true;}af+=xux[i][0],bt+=xux[i][1];}}return false;
}
int bfs(int Bx,int By){vector<int>dis[n+5];vector<bool>vis[n+5];for(int i=1;i<=n+3;i++){for(int j=0;j<=m+1;j++){dis[i].push_back(0);vis[i].push_back(false);}}queue<pair<int,int>>q;q.push({Bx,By});vis[Bx][By]=true;while(q.size()){auto p=q.front();q.pop();if(check(p.first,p.second)){return dis[p.first][p.second];}for(int i=0;i<4;i++){int dx=p.first+xyx[i][0],dy=p.second+xyx[i][1];if(dx&&dy&&dx<=n&&dy<=m&&!vis[dx][dy]&&a[dx][dy]!='X'){dis[dx][dy]=dis[p.first][p.second]+1,vis[dx][dy]=true;q.push({dx,dy});}}}return -1;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){a[i].push_back(0);for(int j=1;j<=m;j++){char x;cin>>x;a[i].push_back(x);}}while(true){cin>>Ex>>Ey>>Bx>>By;if(!Bx||!By||!Ex||!Ey){return 0;}int tmp=bfs(Bx,By);cout<<(tmp==-1?"Poor Harry":to_string(tmp))<<'\n';}return 0;
}

P.S.：呃……我写的时候把方向写错了。

解法2

$n\times m\le 16384$ ，可以考虑用一维数组进行存储。

我们进行“降维打击”，从二维坐标转化为一维坐标，比如说有一个网格：

$(1,1)$	$(1,2)$	$(1,3)$	$(1,4)$
$(2,1)$	$(2,2)$	$(2,3)$	$(2,4)$
$(3,1)$	$(3,2)$	$(3,3)$	$(3,4)$
$(4,1)$	$(4,2)$	$(4,3)$	$(4,4)$

将其转化为一维坐标：

$1$	$2$	$3$	$4$
$5$	$6$	$7$	$8$
$9$	$10$	$11$	$12$
$13$	$14$	$15$	$16$

具体来说，对于一个二维坐标 $(x,y)$ ，其一维坐标为 $(x-1)\times m+y$ 。

其他的地方就跟二维的写法一样了。

实现

#include<bits/stdc++.h>
using namespace std;
int n,m,Bx,By,Ex,Ey,dis[17005],xux[8][3]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}},xyx[5][3]={{-1,0},{1,0},{0,1},{0,-1}};
char a[17005];
bool vis[17005];
int XY(int dx,int dy){return (dx-1)*m+dy;
}
bool check(int dx,int dy){for(int i=0;i<8;i++){int af=dx,bt=dy;while(true){if(af<1||bt<1||af>n||bt>m||a[XY(af,bt)]=='X'){break;}if(af==Ex&&bt==Ey){return true;}af+=xux[i][0],bt+=xux[i][1];}}return false;
}
int bfs(int Bx,int By){fill(vis,vis+n*m+5,false);queue<pair<int,int> >q;q.push({Bx,By});vis[XY(Bx,By)]=true,dis[XY(Bx,By)]=0;while(q.size()){auto p=q.front();q.pop();if(check(p.first,p.second)){return dis[XY(p.first,p.second)];}for(int i=0;i<4;i++){int dx=p.first+xyx[i][0],dy=p.second+xyx[i][1];if(dx&&dy&&dx<=n&&dy<=m&&!vis[XY(dx,dy)]&&a[XY(dx,dy)]!='X'){dis[XY(dx,dy)]=dis[XY(p.first,p.second)]+1,vis[XY(dx,dy)]=true;q.push({dx,dy});}}}return -1;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[XY(i,j)];}}while(true){cin>>Ex>>Ey>>Bx>>By;if(!Bx||!By||!Ex||!Ey){return 0;}int tmp=bfs(Bx,By);cout<<(tmp==-1?"Poor Harry":to_string(tmp))<<'\n';}return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/26782.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！