fork download
copy 
  1. # your code goes here
  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. size=sz-1
  38. sz-=1
  39. while (row<sz and col<sz-1) :
  40.     max_abs=abs(matrix[row][col]) 
  41.     next_row=row
  42.     for i in range (row+1,sz):
  43.         cur_abs=abs(matrix [i][col]) 
  44.         if(cur_abs>max_abs):
  45.             max_abs=cur_abs
  46.             next_row=i
  47.     if(max_abs==0):
  48.         col+=1
  49.         continue
  50.     for i in range (sz) :
  51.         matrix[row][i], matrix[next_row][i]=matrix[next_row][i], matrix[row][i] 
  52.     for i in range (row+1,sz):
  53.         if(matrix[i] [col]!=0):
  54.             GCD=gcd(matrix [row] [col], matrix[i] [col] )
  55.             LCM=matrix [row] [col] *matrix[i] [col] //GCD
  56.             m1=LCM//matrix[row] [col] 
  57.             m2=LCM//matrix[i] [col] 
  58.             det_denom*=m1*m2
  59.             for j in range (col, sz) :
  60.                 matrix[row][j]*=m1
  61.                 matrix[i][j]*=m2
  62.                 matrix[i][j]-=matrix[row][j] 
  63.     row+=1
  64.     col+=1
  65.  
  66. main_d=[] 
  67. for i in range (sz):
  68.     cur=matrix[i] [i] 
  69.     if(cur!=0):
  70.         main_d. append (cur) 
  71. if(len(main_d)==0):
  72.     det=0;
  73. for i in main_d :
  74.     det*=i
  75. M=10**9    
  76. det=(abs(det//det_denom))
  77. if(sz==0):
  78.     det=1
  79. print(str(det) )
Success #stdin #stdout 0.01s 33144KB
comments (?)
stdin
copy 
4 4
....
....
....
....
stdout
copy 
100352
https://ideone.com/5H6ARH
language:
Python 3 (python  3.9.5)
created:
6 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!