fork(1) download 
  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. if(n==1 and m==1):
  15.     if(house[0][0]=='.'):
  16.         print (1)
  17.     else:
  18.         print (0)
  19.     from sys import exit 
  20.     exit()      
  21. from fractions import gcd
  22. matrix=[[0 for i in range (sz)] for i in range (sz)] 
  23. for x in range (sz):
  24.     order=place[x] 
  25.     i=order//m
  26.     j=order%m
  27.     if(j>0 and house[i][j-1]=='.'):
  28.         matrix[x][x]-=1
  29.         matrix[x][rev_place[i*m+j-1]]=1
  30.     if(i>0 and house[i-1][j]=='.'):
  31.         matrix[x][x]-=1
  32.         matrix[x][rev_place[(i-1)*m+j]]=1
  33.     if(j<m-1 and house[i][j+1]=='.'):
  34.         matrix[x][x]-=1
  35.         matrix[x][rev_place[i*m+j+1]]=1
  36.     if(i<n-1 and house[i+1][j]=='.'):
  37.         matrix[x][x]-=1
  38.         matrix[x][rev_place[(i+1)*m+j]]=1
  39.  
  40.  
  41. det=1
  42. det_denom=1
  43. row=0
  44. col=0
  45. while (row<sz-1 and col<sz) :
  46.     max_abs=abs(matrix[row][col]) 
  47.     next_row=row
  48.     for i in range (row+1,sz):
  49.         cur_abs=abs(matrix [i][col]) 
  50.         if(cur_abs>max_abs):
  51.             max_abs=cur_abs
  52.             next_row=i
  53.     if(max_abs==0):
  54.         col+=1
  55.         continue
  56.     for i in range (m) :
  57.         matrix[row] [i], matrix[next_row] [i] =matrix[next_row] [i], matrix[row] [i] 
  58.     for i in range (row+1,sz):
  59.         if(matrix[i] [col]!=0):
  60.             GCD=gcd(matrix [row] [col], matrix[i] [col] )
  61.             m1=matrix [i] [col]//GCD
  62.             m2=matrix[row] [col]//GCD
  63.             det_denom*=m1*m2
  64.             for j in range (col, sz) :
  65.                 matrix[row][j]*=m1
  66.                 matrix[i][j]*=m2
  67.                 matrix[i][j]=abs(matrix[i] [j]) - abs(matrix[row][j]) 
  68.     row+=1
  69.     col+=1
  70. main_d=[] 
  71. for i in range (sz):
  72.     cur=matrix[i] [i] 
  73.     if(cur!=0):
  74.         main_d. append (cur) 
  75. if(len(main_d)==0):
  76.     det=0;
  77. for i in main_d :
  78.     det*=i
  79.  
  80. M=10**9    
  81. det=(abs(det//det_denom))%M
  82. print(det)
Time limit exceeded #stdin #stdout 5s 41888KB
comments (?)
stdin 
9 9
.........
.........
.........
.........
.........
.........
.........
.........
.........
stdout 
Standard output is empty
https://ideone.com/bHtkjS
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!