本文共 2168 字，大约阅读时间需要 7 分钟。

Switch the Lamp On

题目

解析

显然，这一道题中，每个元件都可以旋转，因此本题等价于一道01BFS，只需使用deque即可

code(洛谷):

#include
   
    #include
    
     #include
     
      #include
      
       #define int long long#define mp make_pair using namespace std;int n,m,ans[510][510],dx[4]={
   -1,1,1,-1},dy[4]={
   1,1,-1,-1},tot=0,tx,ty,sx,sy;inline bool check(int x,int y){
   return 0<=x&&x<=n&&0<=y&&y<=m;}char c[510][510];pair
       
         o2;deque 
        
         
           > a;bool ed[510][510][4],u[510][510];signed main(){ memset(ans,0x7f,sizeof(ans)); scanf("%lld%lld",&n,&m),ans[0][0]=0; if((m-n)&1){ printf("NO SOLUTION");return 0;} for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)for(int k=0;k<=3;++k)ed[i][j][k]=1; for(int i=0;i
          
           >c[i][j]; if(c[i][j]=='/')ed[i+1][j][0]=ed[i][j+1][2]=0; else ed[i][j][1]=ed[i+1][j+1][3]=0; } a.push_back(mp(0,0)); while(a.size()) { sx=a.front().first,sy=a.front().second,u[sx][sy]=1,a.pop_front(); for(int i=0;i<=3;++i) { tx=sx+dx[i],ty=sy+dy[i]; if(check(tx,ty)&&(!u[tx][ty])) { if(!ed[sx][sy][i]){ if(ans[sx][sy]
          
         
        
       
      
     
    
   

code(ybtoj):

#include
   
    #include
    
     #include
     
      #include
      
       #define int long long#define mp make_pair using namespace std;inline int abs(int x){
   return x>0?x:-x;}int n,m,ans[510][510],dx[4]={
   -1,1,1,-1},dy[4]={
   1,1,-1,-1},tot=0,tx,ty,sx,sy,T;inline bool check(int x,int y){
   return 0<=x&&x<=n&&0<=y&&y<=m;}char c[510][510];pair
       
         o2;deque 
        
         
           > a;bool ed[510][510][4],u[510][510];signed main(){ scanf("%lld",&T); while(T--) { scanf("%lld%lld",&n,&m); memset(ans,0x7f,sizeof(ans)); memset(u,0,sizeof(u)); ans[0][0]=0; for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)for(int k=0;k<=3;++k)ed[i][j][k]=1; for(int i=0;i
          
           >c[i][j]; if(c[i][j]=='/')ed[i+1][j][0]=ed[i][j+1][2]=0; else ed[i][j][1]=ed[i+1][j+1][3]=0; } if(abs(m-n)&1){ printf("NO SOLUTION\n");continue;} a.push_back(mp(0,0)); while(a.size()) { sx=a.front().first,sy=a.front().second,u[sx][sy]=1,a.pop_front(); for(int i=0;i<=3;++i) { tx=sx+dx[i],ty=sy+dy[i]; if(check(tx,ty)&&(!u[tx][ty])) { if(!ed[sx][sy][i]){ if(ans[sx][sy]
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/zhanglili1597895/article/details/118050238 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！