2 条题解
-
0
B17 双端队列BFS Switch the Lamp On
#include <cstring> #include <iostream> #include <algorithm> #include <deque> using namespace std; typedef pair<int,int> PII; const int N=510; int n,m; char e[N][N]; //格内斜边 int d[N][N]; //操作步数 bool vis[N][N]; //判重 char es[]="\\/\\/"; //斜边 左上角开始顺时针记录 int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1}; //格点增量 int ex[]={-1,-1,0,0},ey[]={-1,0,0,-1}; //格子增量 deque<PII> q; //双端队列 int bfs(){ memset(d,0x3f,sizeof d); d[0][0]=0; q.push_back({0,0}); while(q.size()){ PII u=q.front(); q.pop_front(); int x=u.first,y=u.second; //父格点 if(vis[x][y]) continue; //出队优化 vis[x][y]=1; for(int i=0; i<4; i++){ int a=x+dx[i],b=y+dy[i]; //子格点 if(a<0||a>n||b<0||b>m) continue; int ea=x+ex[i],eb=y+ey[i]; //格子 int dd=d[x][y]+(e[ea][eb]!=es[i]); if(dd<d[a][ b]){ //入队优化 d[a][ b]=dd; if(e[ea][eb]!=es[i])q.push_back({a,b}); else q.push_front({a,b}); } } } return d[n][m]; } int main(){ scanf("%d%d",&n,&m); for(int i=0; i<n; i++) scanf("%s",e[i]); int dd=bfs(); if(dd==0x3f3f3f3f) puts("NO SOLUTION"); else printf("%d\n",dd); }scy:
#include<bits/stdc++.h> using namespace std; const int N=510; const int dxy1[4][2]= {{1,1},{-1,-1},{1,-1},{-1,1}};//这是下一个接线点的方向 const int dxy2[4][2]= {{1,1},{0,0},{1,0},{0,1}};//这是dxy1对应方向的格子位置 struct node{int x,y;}; deque<node> q;//双端队列 int t,n,m,ans=1e8,dis[N][N]; char s[N][N]; int check(int x,int y){return x>=0 && x<=n && y>=0 && y<=m;}//范围内 void bfs() { memset(dis,0x3f,sizeof(dis));//初始化最大值 q.push_front(node {0,0});//(0,0)开始,也可以是(n,m)点开始 dis[0][0]=0; while(q.size()) { node now=q.front(); q.pop_front(); for(int i=0;i<=3;i++)//四种方向，0和1对应'\'，0表示左上到右下，1表示右下到左上；2和3对应'/'，2表示左下到右上，3表示右上到左下； { int xx=now.x+dxy1[i][0],yy=now.y+dxy1[i][1];//下个点的位置 if(!check(xx,yy))continue; int gx=now.x+dxy2[i][0],gy=now.y+dxy2[i][1];//经过格子的位置 int dd=(s[gx][gy] != (i<=1? '\\':'/'));//如果经过格子的开关和走的方向符合则dd=0，否则需要转开关就是dd=1 if(dis[xx][yy]>dis[now.x][now.y]+dd)//check成功,并且当前值更加优秀 { dis[xx][yy]=dis[now.x][now.y]+dd; if(dd==0)q.push_front(node{xx,yy});//不需要转开关的点放队头。可以优先扩展出去（优先搜索） else q.push_back(node{xx,yy}); //需要转开关的点放队尾（代表不优先搜索） } } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>s[i][j]; bfs(); if(dis[n][m]<1e8)cout<<dis[n][m]<<endl;//如果找到了方案 else cout<<"NO SOLUTION"<<endl; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:05:58
B17 双端队列BFS Switch the Lamp On
#include <cstring> #include <iostream> #include <algorithm> #include <deque> using namespace std; typedef pair<int,int> PII; const int N=510; int n,m; char e[N][N]; //格内斜边 int d[N][N]; //操作步数 bool vis[N][N]; //判重 char es[]="\\/\\/"; //斜边 左上角开始顺时针记录 int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1}; //格点增量 int ex[]={-1,-1,0,0},ey[]={-1,0,0,-1}; //格子增量 deque<PII> q; //双端队列 int bfs(){ memset(d,0x3f,sizeof d); d[0][0]=0; q.push_back({0,0}); while(q.size()){ PII u=q.front(); q.pop_front(); int x=u.first,y=u.second; //父格点 if(vis[x][y]) continue; //出队优化 vis[x][y]=1; for(int i=0; i<4; i++){ int a=x+dx[i],b=y+dy[i]; //子格点 if(a<0||a>n||b<0||b>m) continue; int ea=x+ex[i],eb=y+ey[i]; //格子 int dd=d[x][y]+(e[ea][eb]!=es[i]); if(dd<d[a][ b]){ //入队优化 d[a][ b]=dd; if(e[ea][eb]!=es[i])q.push_back({a,b}); else q.push_front({a,b}); } } } return d[n][m]; } int main(){ scanf("%d%d",&n,&m); for(int i=0; i<n; i++) scanf("%s",e[i]); int dd=bfs(); if(dd==0x3f3f3f3f) puts("NO SOLUTION"); else printf("%d\n",dd); }
scy:#include<bits/stdc++.h> using namespace std; const int N=510; const int dxy1[4][2]= {{1,1},{-1,-1},{1,-1},{-1,1}};//这是下一个接线点的方向 const int dxy2[4][2]= {{1,1},{0,0},{1,0},{0,1}};//这是dxy1对应方向的格子位置 struct node{int x,y;}; deque<node> q;//双端队列</p>int t,n,m,ans=1e8,dis[N][N]; char s[N][N];
int check(int x,int y){return x>=0 && x<=n && y>=0 && y<=m;}//范围内 void bfs() { memset(dis,0x3f,sizeof(dis));//初始化最大值 q.push_front(node {0,0});//(0,0)开始,也可以是(n,m)点开始 dis[0][0]=0; while(q.size()) { node now=q.front(); q.pop_front(); for(int i=0;i<=3;i++)//四种方向，0和1对应''，0表示左上到右下，1表示右下到左上；2和3对应'/'，2表示左下到右上，3表示右上到左下； { int xx=now.x+dxy1[i][0],yy=now.y+dxy1[i][1];//下个点的位置 if(!check(xx,yy))continue; int gx=now.x+dxy2[i][0],gy=now.y+dxy2[i][1];//经过格子的位置 int dd=(s[gx][gy] != (i<=1? '\':'/'));//如果经过格子的开关和走的方向符合则dd=0，否则需要转开关就是dd=1 if(dis[xx][yy]>dis[now.x][now.y]+dd)//check成功,并且当前值更加优秀 { dis[xx][yy]=dis[now.x][now.y]+dd; if(dd==0)q.push_front(node{xx,yy});//不需要转开关的点放队头。可以优先扩展出去（优先搜索） else q.push_back(node{xx,yy}); //需要转开关的点放队尾（代表不优先搜索）
} } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>s[i][j]; bfs(); if(dis[n][m]<1e8)cout<<dis[n][m]<<endl;//如果找到了方案 else cout<<"NO SOLUTION"<<endl; return 0; }
- 1
