首页 > 代码库 > noip 01迷宫（BFS+记忆化）
noip 01迷宫（BFS+记忆化）
题目链接：https://www.luogu.org/problem/show?pid=1141
题意:给出一个仅由数字0与1组成的n×n格迷宫。放0的那一格可以4个方向走到放1那一格，1也是四个方向走到放0的那一格。算上本身的那格。求最多能移动多少格子。
数据比较大，如果直接用bfs搜的话会暴时。所以需要每次搜索完都记录一下。
1 #include <iostream> 2 #include <algorithm> 3 #include <queue> 4 using namespace std; 5 6 const int maxn=1111; 7 typedef pair<int,int> P; 8 9 char maze[maxn][maxn];10 int vis[maxn][maxn];11 long long ans[maxn*maxn];12 int dx[4]={1,-1,0,0};13 int dy[4]={0,0,1,-1};14 int n,m; 15 16 int bfs(int turn,int sx,int sy){17 queue <P> que;18 P p;19 20 que.push(P(sx,sy));21 vis[sx][sy]=turn;22 23 long long cnt=0;24 while(que.size()){25 p=que.front();que.pop();26 cnt++;27 for(int i=0;i<4;i++){28 int nx=p.first+dx[i],ny=p.second+dy[i];29 if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&maze[nx][ny]!=maze[p.first][p.second]&&vis[nx][ny]==0){30 que.push(P(nx,ny));31 vis[nx][ny]=turn;32 }33 }34 }35 return cnt;36 }37 38 int main(){39 int sx,sy;40 cin>>n>>m;41 for(int i=1;i<=n;i++)42 for(int j=1;j<=n;j++)43 cin>>maze[i][j];44 45 //每一次访问过的点,他们能遍历的最多格子是一样的.记忆化一下. 46 for(int i=1;i<=m;i++){47 cin>>sx>>sy;48 if(!vis[sx][sy]) {ans[i]=bfs(i,sx,sy);cout<<ans[i]<<endl;}49 else {ans[i]=ans[vis[sx][sy]];cout<<ans[i]<<endl;}50 }51 return 0;52 }
noip 01迷宫（BFS+记忆化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。