LOJ#2632. 「BalticOI 2011 Day1」打开灯泡 Switch the Lamp On

译自 BalticOI 2011 Day1 T3「Switch the Lamp On」
有一种正方形的电路元件，在它的两组相对顶点中，有一组会用导线连接起来，另一组则不会。
有

Casper is designing an electronic circuit on a $N\timesM rectangular grid plate. There are N\timesM square tiles that are aligned to the grid on the plate. Two (out of four) opposite corners of each tile are connected by a wire.A power source is connected to the top left corner of the plate. A lamp is connected to the bottom right corner of the plate. The lamp is on only if there is a path of wires connecting power source to lamp. In order to switch the lamp on, any number of tiles can be turned by 90° (in both directions).In the picture above the lamp is off. If any one of the tiles in the second column from the right is turned by 90° , power source and lamp get connected, and the lamp is on.Write a program to find out the minimal number of tiles that have to be turned by 90° to switch the lamp on.$

第一行有两个整数 $\ 或 /，表示正方形元件上导线的连接方向。$

The first line of input contains two integer numbers $\ or / – which indicate the direction of the wire connecting the opposite vertices of the corresponding tile.$

输出共一行，若有解则输出一个整数，表示至少要旋转多少个正方形元件才能让电源与灯泡连通；若无解则输出 NO SOLUTION。

There must be exactly one line of output. If it is possible to switch the lamp on, this line must contain only one integer number: the minimal number of tiles that have to be turned to switch on the lamp. If it is not possible, output the string: NO SOLUTION

样例输入

3 5
\\/\\
\\///
/\\\\

样例输出

对于

题解

唔...这题$spfa+SLF$跑的飞快

因为跑bfs要判的东西貌似很多的样子所以我直接连边跑spfa了

对于能够直接走的那就连一条0边，不能直接走就连1边

然后注意坐标位置的取值...

因为边权只有0和1所以SLF在这里很有用

最后就是空间要乘个8倍

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f 
#define il inline 

#define in(a) a=read()
#define out(a) printf( "%d" , a ) 
#define outn(a) out(a),putchar('\n')

#define I_int int
inline I_int read() {
    
    I_int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    return x * f ;
}
#undef I_int

using namespace std ;

const int N = 510 ;
const int M = (500*500+10)*4 ;
const int dx[] = {0,0,1,-1};
const int dy[] = {-1,1,0,0};

char a[ N ][ N ] ;
int n , m ;
int head[ M ] , d[ M ] , cnt , vis[ M ] ;
struct node {
    int to , nxt , v ;
} e[ M << 1 ] ;

void ins( int u , int v , int w ) {
    e[ ++ cnt ].to = v ;
    e[ cnt ].nxt = head[ u ] ;
    e[ cnt ].v = w ;
    head[ u ] = cnt ;
}

bool check( int x , int y ) {
    if( x < 0 || x > n || y < 0 || y > m ) return 0 ;
    return 1 ;
}

int zb( int x , int y ) {
    return (x-1)*(m+1)+y ;
}

deque<int>q;

void spfa() {
    vis[ 1 ] = 1 ;
    for( int i = 1 ; i <= (n+1)*(m+1) ; i ++ ) d[ i ] = inf ;
    d[ 1 ] = 0 ;
    q.push_front(1);
    while( !q.empty() ) {
        int u = q.front() ; q.pop_front() ;
        vis[ u ] = 0 ;
        for( int i = head[ u ] ; i ; i = e[ i ].nxt ) {
            int v = e[ i ].to ;
            if( d[ v ] > d[ u ] + e[ i ].v ) {
                d[ v ] = d[ u ] + e[ i ].v ;
                if( !vis[ v ] ) {
                    vis[ v ] = 1 ; 
                    if(!e[i].v) q.push_front(v);
                    else q.push_back(v) ;
                }
            }
        }
    }
    if( d[zb(n,m)] == inf ) puts("NO SOLUTION") ;
    else outn( d[ zb(n+1,m+1) ] ) ;
}

int main() {
    in( n ) ; in( m ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        scanf( "%s" , a[ i ] + 1 ) ;
        for( int j = 1 ; j <= m ; j ++ ) {
            if( a[ i ][ j ] == '\\' ) {
                ins( zb(i,j+1) , zb(i+1,j) , 1 ) , ins( zb(i+1,j) , zb(i,j+1) , 1 ) ;
                ins( zb(i,j) , zb(i+1,j+1) , 0 ) , ins( zb(i+1,j+1) , zb(i,j) , 0 ) ;
            }
            if( a[ i ][ j ] == '/' ) {
                ins( zb(i,j+1) , zb(i+1,j) , 0 ) , ins( zb(i+1,j) , zb(i,j+1) , 0 ) ;
                ins( zb(i,j) , zb(i+1,j+1) , 1 ) , ins( zb(i+1,j+1) , zb(i,j) , 1 ) ;
            }
        }
    }
    spfa() ;
}

LOJ#2632. 「BalticOI 2011 Day1」打开灯泡 Switch the Lamp On

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

题解