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 decimal import *
  15. from decimal import Decimal as d 
  16. getcontext().prec=1450
  17. matrix=[[d(0) for i in range (sz)] for i in range (sz)] 
  18. for x in range (sz):
  19.     order=place[x] 
  20.     i=order//m
  21.     j=order%m
  22.     if(j>0 and house[i][j-1]=='.'):
  23.         matrix[x][x]-=d(1)
  24.         matrix[x][rev_place[i*m+j-1]]=d(1)
  25.     if(i>0 and house[i-1][j]=='.'):
  26.         matrix[x][x]-=d(1)
  27.         matrix[x][rev_place[(i-1)*m+j]]=d(1)
  28.     if(j<m-1 and house[i][j+1]=='.'):
  29.         matrix[x][x]-=d(1)
  30.         matrix[x][rev_place[i*m+j+1]]=d(1)
  31.     if(i<n-1 and house[i+1][j]=='.'):
  32.         matrix[x][x]-=d(1)
  33.         matrix[x][rev_place[(i+1)*m+j]]=d(1)
  34.  
  35.  
  36. det=d(1) 
  37. row=0
  38. col=0
  39. eps=d(1)/d(10000000) 
  40. while (row<sz-1 and col<sz) :
  41.     max_abs=abs(matrix[row][col]) 
  42.     next_row=row
  43.     for i in range (row+1,sz):
  44.         cur_abs=abs(matrix [i][col]) 
  45.         if(cur_abs>max_abs):
  46.             max_abs=cur_abs
  47.             next_row=i
  48.     if(max_abs<eps):
  49.         col+=1
  50.         continue
  51.     for i in range (sz) :
  52.         matrix[row] [i], matrix[next_row] [i] =matrix[next_row] [i], matrix[row] [i] 
  53.     for i in range (row+1,sz):
  54.         coeff=matrix [i] [col]/matrix[row] [col] 
  55.         for j in range (col, sz) :
  56.             matrix [i][j]-=coeff*matrix[row][j]
  57.     row+=1
  58.     col+=1
  59. size=sz
  60. while(sz>1 and abs(matrix[sz-1][sz-1])<eps):
  61.     sz-=1
  62. for i in range (sz) :
  63.     det*=d(abs(matrix[i][i])+eps) 
  64. M=1000*1000*1000
  65. ans=(int(det+eps))%M 
  66. if(size==1):
  67.     ans=1
  68. print(ans)
Success #stdin #stdout 0.02s 33152KB
comments (?)
stdin
copy 
2 2
.. 
..
stdout
copy 
4
https://ideone.com/7nPKN0
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!