fork download
copy 
  1. #It took pretty long time... 
  2. n, m=map (int, input (). split ()) 
  3. house=[]
  4. place={}
  5. rev_place={} 
  6. sz=0
  7. for i in range (n) :
  8.     house.append(input ()) 
  9.     for j in range (m) :
  10.         if(house[i][j] ==".") :
  11.             place[sz]=i*m+j
  12.             rev_place[place[sz]]=sz
  13.             sz+=1
  14. from fractions import gcd
  15. matrix=[[0 for i in range (sz)] for i in range (sz)] 
  16. for x in range (sz):
  17.     order=place[x] 
  18.     i=order//m
  19.     j=order%m
  20.     if(j>0 and house[i][j-1]=='.'):
  21.         matrix[x][x]-=1
  22.         matrix[x][rev_place[i*m+j-1]]=1
  23.     if(i>0 and house[i-1][j]=='.'):
  24.         matrix[x][x]-=1
  25.         matrix[x][rev_place[(i-1)*m+j]]=1
  26.     if(j<m-1 and house[i][j+1]=='.'):
  27.         matrix[x][x]-=1
  28.         matrix[x][rev_place[i*m+j+1]]=1
  29.     if(i<n-1 and house[i+1][j]=='.'):
  30.         matrix[x][x]-=1
  31.         matrix[x][rev_place[(i+1)*m+j]]=1
  32.  
  33. det=1
  34. det_denom=1
  35. row=0
  36. col=0
  37. sz-=1
  38. while (row<sz and col<sz-1) :
  39.     max_abs=abs(matrix[row][col]) 
  40.     next_row=row
  41.     for i in range (row+1,sz):
  42.         cur_abs=abs(matrix [i][col]) 
  43.         if(cur_abs>max_abs):
  44.             max_abs=cur_abs
  45.             next_row=i
  46.     if(max_abs==0):
  47.         det=0
  48.         break
  49.     for i in range (sz) :
  50.         matrix[row][i], matrix[next_row][i]=matrix[next_row][i], matrix[row][i] 
  51.     for i in range (row+1,sz):
  52.         if(matrix[i] [col]!=0):
  53.             GCD=gcd(matrix [row] [col], matrix[i] [col] )
  54.             LCM=matrix [row] [col] *matrix[i] [col] //GCD
  55.             m1=LCM//matrix[row] [col] 
  56.             m2=LCM//matrix[i] [col] 
  57.             det_denom*=m1*m2
  58.             for j in range (col, sz) :
  59.                 matrix[row][j]*=m1
  60.                 matrix[i][j]*=m2
  61.                 matrix[i][j]-=matrix[row][j] 
  62.     row+=1
  63.     col+=1
  64.  
  65. for i in range (sz):
  66.     det*=matrix[i][i] 
  67. M=10**9    
  68. det=(abs(det//det_denom))%M
  69. if(sz==0):
  70.     det=1
  71. print(str(det) )
Success #stdin #stdout 0.02s 33144KB
comments (?)
stdin
copy 
2 2
..
..
stdout
copy 
4
https://ideone.com/CIEdmo
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!