1 条题解

  • 0
    @ 2023-6-21 20:14:13

    C++ :

    #include<cstdio>
    #define oo 510
    #define op puts("OP")
    #define Mx 999999999
    using namespace std;
    int ddx[5]={0, 0, 1, 1, 0};
    int ddy[5]={0, 0, 0, 1, 1};
    int dx[5]= {0,-1, 1, 1,-1};
    int dy[5]= {0,-1,-1, 1, 1};
    char Map[oo][oo];
    int nx,ny,x[oo*oo],y[oo*oo],Dis[oo][oo];
    bool Visit[oo][oo];
    void Read()
    {
    	scanf("%d%d",&nx,&ny);
    	for(int i=1;i<=nx;++i)
    	{
    		scanf("%s",Map[i]+1);
    	}
    	return ;
    }
    void Work()
    {
    	int Head=0,Tail=1,Flag;
    	x[0]=0,y[0]=0,Dis[0][0]=0;
    	while(Head!=Tail)
    	{
    		if(Head==oo*oo+1)Head=0;
    		//printf("取出%d:(%d,%d),Dis=%d\n",Head,x[Head],y[Head],Dis[ x[Head] ][ y[Head] ]); 
    		int Crent_x=x[Head],Crent_y=y[Head++];
    		Visit[Crent_x][Crent_y]=1;
    		//Visit[Crent_x][Crent_y]=0;
    		//printf("指针指向%d\n",Head);
    		for(int i=1;i<=4;++i)
    		{
    			int xx=Crent_x+dx[i],yy=Crent_y+dy[i];
    			if(Visit[xx][yy]||xx<0||xx>nx||yy<0||yy>ny)continue;
    			if(Map[Crent_x+ddx[i]][Crent_y+ddy[i]]=='/')
    			{
    				if(i&1)Flag=1;
    				else Flag=0;
    			}
    			else 
    			{
    				if(i&1)Flag=0;
    				else Flag=1;
    			}
    			if(!Flag)
    			{
    				
    				if(Head==0)Head=oo*oo+1;
    				x[--Head]=xx;
    				y[Head]=yy;
    				Dis[xx][yy]=Dis[Crent_x][Crent_y];	//printf("找到点%d,%d,消耗为%d,存入%d\n",xx,yy,Flag,Head);printf("指针指向%d\n",Head);
    				//Visit[xx][yy]=1;
    			}
    			else 
    			{
    				//printf("找到点%d,%d,消耗为%d,存入%d\n",xx,yy,Flag,Tail);
    				if(Tail==oo*oo)Tail=0;
    				x[Tail]=xx;
    				y[Tail++]=yy;
    				Dis[xx][yy]= Dis[xx][yy]<Dis[Crent_x][Crent_y]+1? Dis[xx][yy]:Dis[Crent_x][Crent_y]+1;
    				//Visit[xx][yy]=1;
    			}
    			if(xx==nx&&yy==ny)
    			{
    				printf("%d\n",Dis[nx][ny]);
    				return ;
    			}
    		}
    		
    	}
    }
    int main()
    {
    	Read();
    	if((nx+ny)&1){printf("NO SOLUTION\n");return 0;}
    	for(int i=0;i<=nx;++i)for(int j=0;j<=ny;++j)Dis[i][j]=Mx;
    	Work();
    	
    	return 0;
    }
    
    • 1

    #10026. 「一本通 1.4 例 1」电路维修「BalticOI 2011 Day1」打开灯泡 Switch the Lamp On

    信息

    ID
    1066
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    5
    已通过
    2
    上传者