<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> class Solution ( object ) : <EOL> def __init__ ( self ) : <EOL> self . dirs = ( ( - <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:0> , - <NUM_LIT:1> ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) ) <EOL> def wallsAndGates ( self , mat ) : <EOL> """<STR_LIT>""" <EOL> q = [ ( i , j ) for i , row in enumerate ( mat ) for j , val in enumerate ( row ) if val == <NUM_LIT:0> ] <EOL> for i , j in q : <EOL> for d in self . dirs : <EOL> i1 , j1 = i + d [ <NUM_LIT:0> ] , j + d [ <NUM_LIT:1> ] <EOL> if <NUM_LIT:0> <= i1 < len ( mat ) and <NUM_LIT:0> <= j1 < len ( mat [ <NUM_LIT:0> ] ) and mat [ i1 ] [ j1 ] > mat [ i ] [ j ] + <NUM_LIT:1> : <EOL> mat [ i1 ] [ j1 ] = mat [ i ] [ j ] + <NUM_LIT:1> <EOL> q . append ( ( i1 , j1 ) ) <EOL> class Solution_slow ( object ) : <EOL> def __init__ ( self ) : <EOL> self . dirs = ( ( - <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:0> , - <NUM_LIT:1> ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) ) <EOL> def wallsAndGates ( self , rooms ) : <EOL> """<STR_LIT>""" <EOL> if not rooms : return <EOL> m = len ( rooms ) <EOL> if not m : return <EOL> n = len ( rooms [ <NUM_LIT:0> ] ) <EOL> for i in xrange ( m ) : <EOL> for j in xrange ( n ) : <EOL> if rooms [ i ] [ j ] == <NUM_LIT:0> : <EOL> self . bfs_deque ( rooms , i , j ) <EOL> def bfs ( self , rooms , x , y ) : <EOL> m = len ( rooms ) <EOL> n = len ( rooms [ <NUM_LIT:0> ] ) <EOL> level = <NUM_LIT:0> <EOL> q = [ ( x , y ) ] <EOL> while q : <EOL> l = len ( q ) <EOL> for idx in xrange ( l ) : <EOL> i , j = q [ idx ] <EOL> rooms [ i ] [ j ] = min ( rooms [ i ] [ j ] , level ) <EOL> for d in self . dirs : <EOL> i_t = i + d [ <NUM_LIT:0> ] <EOL> j_t = j + d [ <NUM_LIT:1> ] <EOL> if <NUM_LIT:0> <= i_t < m and <NUM_LIT:0> <= j_t < n and rooms [ i_t ] [ j_t ] != - <NUM_LIT:1> and rooms [ i_t ] [ j_t ] >= level + <NUM_LIT:1> : <EOL> q . append ( ( i_t , j_t ) ) <EOL> q = q [ l : ] <EOL> level += <NUM_LIT:1> <EOL> def bfs_deque ( self , rooms , x , y ) : <EOL> from collections import deque <EOL> m = len ( rooms ) <EOL> n = len ( rooms [ <NUM_LIT:0> ] ) <EOL> q = deque ( ) <EOL> q . append ( ( x , y , <NUM_LIT:0> ) ) <EOL> while q : <EOL> i , j , level = q . popleft ( ) <EOL> rooms [ i ] [ j ] = min ( rooms [ i ] [ j ] , level ) <EOL> for d in self . dirs : <EOL> i_t , j_t = i + d [ <NUM_LIT:0> ] , j + d [ <NUM_LIT:1> ] <EOL> if <NUM_LIT:0> <= i_t < m and <NUM_LIT:0> <= j_t < n and rooms [ i_t ] [ j_t ] != - <NUM_LIT:1> and rooms [ i_t ] [ j_t ] >= level + <NUM_LIT:1> : <EOL> q . append ( ( i_t , j_t , level + <NUM_LIT:1> ) ) <EOL> class Solution_error ( object ) : <EOL> def __init__ ( self ) : <EOL> self . dirs = ( ( - <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:0> , - <NUM_LIT:1> ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) ) <EOL> def wallsAndGates ( self , rooms ) : <EOL> """<STR_LIT>""" <EOL> if not rooms : return <EOL> m = len ( rooms ) <EOL> if not m : return <EOL> n = len ( rooms [ <NUM_LIT:0> ] ) <EOL> visited = [ [ False for _ in xrange ( n ) ] for _ in xrange ( m ) ] <EOL> for i in xrange ( m ) : <EOL> for j in xrange ( n ) : <EOL> if not visited [ i ] [ j ] : <EOL> self . dfs ( rooms , i , j , visited ) <EOL> def dfs ( self , rooms , i , j , visited ) : <EOL> if not visited [ i ] [ j ] : <EOL> visited [ i ] [ j ] = True <EOL> for d in self . dirs : <EOL> nxt_i = i + d [ <NUM_LIT:0> ] <EOL> nxt_j = j + d [ <NUM_LIT:1> ] <EOL> if rooms [ nxt_i ] [ nxt_j ] != - <NUM_LIT:1> : <EOL> rooms [ nxt_i ] [ nxt_j ] = min ( rooms [ nxt_i ] [ nxt_j ] , self . dfs ( rooms , nxt_i , nxt_j , visited ) + <NUM_LIT:1> ) <EOL> return rooms [ nxt_i ] [ nxt_j ] </s>
