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.  
  34. det=1
  35. det_denom=1
  36. row=0
  37. col=0
  38. while (row<sz-1 and col<sz) :
  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.         col+=1
  48.         continue
  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.             m1=matrix [i] [col]//GCD
  55.             m2=matrix[row] [col]//GCD
  56.             det_denom*=m1*m2
  57.             for j in range (col, sz) :
  58.                 matrix[row][j]*=m1
  59.                 matrix[i][j]*=m2
  60.                 matrix[i][j]=abs(matrix[i] [j]) - abs(matrix[row][j]) 
  61.     row+=1
  62.     col+=1
  63. main_d=[] 
  64. for i in range (sz):
  65.     cur=matrix[i] [i] 
  66.     if(cur!=0):
  67.         main_d. append (cur) 
  68. if(len(main_d)==0):
  69.     det=0;
  70. for i in main_d :
  71.     det*=i
  72.  
  73. M=10**9    
  74. det=(abs(det//det_denom))%M
  75. if det==0 and sz==1:
  76.     det=1
  77. print(det)
Success #stdin #stdout 0.03s 33440KB
comments (?)
stdin
copy 
3 3
... 
... 
...
stdout
copy 
676
https://ideone.com/KGeDMM
WA #6
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!