Input
2 2
..
..

Output
1


Input
12 12
************
************
************
******..****
******..****
************
************
************
************
************
************
************

Output
1


Input
2 4
....
****

Output
0


Input
4 2
.*
.*
.*
.*

Output
0


Input
2 5
..*..
..*..

Output
0


Input
5 2
..
..
**
..
..

Output
0


Input
12 12
............
............
............
............
............
............
............
............
............
............
............
...........*

Output
0


Input
6 6
......
......
..**..
..**..
......
......

Output
14


Input
6 6
......
......
......
......
......
......

Output
1072


Input
12 12
............
............
............
............
............
............
............
............
............
............
............
............

Output
1076226888605605706

 Can you help me with test 28?

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 12;
const int maxst = 50000 + 5;

const int orz = 19260817;

struct Hash
{
    int cnt[orz];
    ull val[orz];
    int head[orz], nxt[orz], sz;

    void inline insert(ull u, int c)
    {
        int v = u % orz, i, lst = 0;
        for(i = head[v]; i; lst = i, i = nxt[i]) if(val[i] == u) break;
        if(i) cnt[i] = c;
        else {
            if(lst) nxt[lst] = ++sz;
            else head[v] = ++sz;
            val[sz] = u, cnt[sz] = c;
        }
    }

    int inline find(ull u)
    {
        int v = u % orz, i;
        for(i = head[v]; i; i = nxt[i]) if(val[i] == u) return cnt[i];
        return 0;
    }
} vti;
ull itv[maxst]; int tot;

int n, m;
char board[maxn + 3][maxn + 3];
int ptn[maxst][maxn + 2];
int fi, fj;

void inline getptn(int id)
{
    ull st = itv[id];
    int stk[maxn], cnt = 0;
    for(int i = 1; st; st >>= 2, ++i) {
        int p = st & 3;
        if(p == 1) stk[++cnt] = i;
        else  if(p == 2) ptn[id][i] = stk[cnt], ptn[id][stk[cnt--]] = i;
    }
}

void dfs(ull st, int dep, int k)
{
    if(dep > n + 1) {
        if(k) return;
        itv[++tot] = st;
        vti.insert(st, tot);
        return;
    }
    if(k > n + 1 - dep + 1) return;
    dfs(st, dep + 1, k); // #
    dfs(st | (1 << (2 * (dep - 1))), dep + 1, k + 1); // (
    if(k) dfs(st | (2 << (2 * (dep - 1))), dep + 1, k - 1); // )
}

void inline Init()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", board[i] + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(board[i][j] == '*') board[i][j] = 0;
            else board[i][j] = 1;
    dfs(0, 1, 0);
    for(int i = 1; i <= tot; ++i) getptn(i);
//    printf("tot = %d\n", tot);
    for(int i = n; i; --i) {
        for(int j = m; j; --j) {
            if(board[i][j]) {
                fi = i, fj = j;
//                printf("fi = %d, fj = %d\n", fi, fj);
                return;
            }
        }
    }
}

ll f[maxn + 2][maxn + 2][maxst];

ull inline fillas(ull S, int k, int c) {
    S &= ~(3 << (2 * (k - 1)));    // set zero
    S |= c << (2 * (k - 1));    // set c
    return S;
}

void inline Solve()
{
    f[0][m][vti.find(0)] = 1;
    for(int i = 0; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            for(int k = 1; k <= tot; ++k) {
                ull st = itv[k];
                if(!f[i][j][k]) continue;    // cut (=^o^=)
//                printf("f[%d][%d][%d] = %lld\n", i, j, k, f[i][j][k]);
                int tj = j + 1, ti = i; if(tj > m) tj = 1, ti = i + 1; // get target.

                int left = (st >> (2 * (tj - 1))) & 3;    // left plug
                int top = (st >> (2 * tj)) & 3;            // top plug
//                printf("[%d, %d] -> [%d, %d] with left = %d, top = %d.\n", i, j, ti, tj, left, top);

                if(!left && !top) {    // no plug
                    if(!board[ti][tj]) {    // if cannot
                        ull S = st;    // do nothing
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    } else if(board[ti + 1][tj] && board[ti][tj + 1]) {    // can ?
                        ull S = fillas(fillas(st, tj, 1), tj + 1, 2); // fill it
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }

                else if(left == 1 && top == 1) { // double left
                    int pp = ptn[k][tj + 1]; // get partner
                    ull S = fillas(fillas(fillas(st, tj, 0), tj + 1, 0), pp, 1);
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 2 && top == 2) {    // double right
                    int pp = ptn[k][tj];    // get partner
                    ull S = fillas(fillas(fillas(st, tj, 0), tj + 1, 0), pp, 2);
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 2 && top == 1) {    // right and left
                    ull S = fillas(fillas(st, tj, 0), tj + 1, 0);    // connect them directly
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 1 && top == 2) {    // left and right
                    if(ti == fi && tj == fj) {    // end block only
                        ull S = fillas(fillas(st, tj, 0), tj + 1, 0);    // connect them directly
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }

                else {    // one have plug but another no
//                    printf("ah?\n");
                    if(board[ti + 1][tj]) {    // if down can to
                        ull S = fillas(fillas(st, tj, left + top), tj + 1, 0);    // set
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
//                        printf("%d %llu\n", vti.find(S), S);
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                    if(board[ti][tj + 1]) {    // if right canto
                        ull S = fillas(fillas(st, tj, 0), tj + 1, left + top);    // set
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }
            }
        }
    }
}

int main()
{
    Init();
/*    for(int i = 1; i <= tot; ++i) {
        printf("id: %d, st: %llu\n", i, itv[i]);
    }*/
    Solve();
    printf("%lld\n", f[n][m][1]);
    return 0;
}

I think this is very interesting and hard problem
so who can tell me the solution of this problem
what is the author's solution

GET BIGER HASH NUM !!!!
If your hash number isn't big enough, you will end up with an endless loop.

void Read()
{    int i,j;char In[NUM];
    scanf("%d%d",&n,&m);
    for(i=0;i<=n+1;i++)
     for(j=0;j<=m+1;j++)Map[i][j]=1;
    for(i=1;i<=n;i++)
    { scanf("%s",In);
      for(j=1;j<=m;j++)
      { Map[i][j]=(In[j-1]=='*');
        if(!Map[i][j]){tx=i;ty=j;}
      }
    }
}
this Read() got AC
I think it's probably because the '\n' at the end of the line
try this change:

void Read()
{    int i,j;char ch;
    scanf("%d%d",&n,&m);
    for(i=0;i<=n+1;i++)
     for(j=0;j<=m+1;j++)Map[i][j]=1;
    for(i=1;i<=n;i++)
    { scanf("%c",&ch);
      for(j=1;j<=m;j++)
      { scanf("%c",&ch);
        Map[i][j]=(ch=='*');
        if(!Map[i][j]){tx=i;ty=j;}
      }
    }
}
I tested and both can AC this problem.

why it happened!!??

because of this, i debug for a long time but no effect.

That's magical and I don't think there's any undefined behaviors etc. in my code..
Those who are puzzled in ridiculous WA may try to change the compiler.

I just can't stop tle-ing.
Should I use 4-based?

Edited by author 11.03.2014 15:04

I got a WA while using scanf but got an Accepted when I used cin instead.

I got WA on Test 16,but I don't know why.

why i got Crash (access violation) of test 17

10 8
**....**
**....**
**....**
**....**
********
**....**
**....**
**....**
**....**
********

===>  0  or     6    or     6*6 = 36 ??

Firstly,I used int64,but I get 'Memory Limit Exceeded'.
Then I used hash,but I get 'Wrong Answer' on #9.
It is driving me mad!
What's testdata #9?

const
  zs=699967;
type
  size=record
    di,zhuan:longint;
    x,y:integer;
  end;
var
  dz:array[0..14329,1..2] of longint;
  dui:Array[0..14329,1..2] of int64;
  hash:array[0..700000] of size;
  xx,s1,s2,pd,n,m,i1,i2,zhuan,l1,l2,nzhuan,k:longint;
  d:Array[1..2] of longint;
  map:Array[0..13,0..13] of  char;
  san:array[0..13] of longint;
  zhi:int64;
  i,j,ii:longint;
procedure swap(var a,b:longint);
var
  t:longint;
begin
  t:=a; a:=b; b:=t;
end;
function zb(nzhuan:longint):longint;
begin
  zb:=nzhuan mod  zs;
  while (hash[zb].x=i) and (hash[zb].y=j) and (hash[zb].zhuan<>nzhuan) do
  begin
    inc(zb);
    zb:=zb mod zs;
  end;
end;


procedure jiaru(nzhuan:longint;zhi:int64);
var
  nzb:longint;
begin
  if ((map[i+1,j]='*')and (nzhuan div san[j-1] mod 3>0))
    or ((map[i,j+1]='*')and (nzhuan div san[j] mod 3>0)) then
    exit;
  nzb:=zb(nzhuan);
  if (hash[nzb].x<>i)or (hash[nzb].y<>j) then
  begin
    inc(d[i2]);
    dz[d[i2],i2]:=nzhuan;
    dui[d[i2],i2]:=zhi;
    hash[nzb].x:=i; hash[nzb].y:=j;
    hash[nzb].di:=d[i2];
    hash[nzb].zhuan:=nzhuan;
  end else begin
    inc(dui[hash[nzb].di,i2],zhi);
  end;
end;
begin
  san[0]:=1;
  for i:=1 to 13 do san[i]:=san[i-1]*3;
  readln(n,m);
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      read(map[i,j]);
      if i=1 then map[i-1,j]:='*';
      if i=n then map[i+1,j]:='*';
      if j=1 then map[i,j-1]:='*';
      if j=m then map[i,j+1]:='*';
    end;
    readln;
  end;
  map[0,0]:='*'; map[0,m]:='*';
  for i:=0 to 600000 do
  hash[i].x:=0;
  dui[1,1]:=1; dz[1,1]:=0;
  i1:=1; i2:=2;
  d[1]:=1;
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      d[i2]:=0;
      for ii:=1 to d[i1] do
      begin
        zhuan:=dz[ii,i1];
        zhi:=dui[ii,i1];
        l1:=zhuan div san[j-1] mod 3;
        l2:=zhuan div san[j] mod 3;
        if l1+l2=3 then
        begin
          if (l1=1)and (l2=2)and ((i<>n) or (j<>m)) then continue;
          nzhuan:=zhuan-san[j-1]*l1-san[j]*l2;
          jiaru(nzhuan,zhi);
        end else
        if l1+l2=0 then
        begin
          if map[i,j]='.' then
          nzhuan:=zhuan+san[j-1]*1+san[j]*2 else
          nzhuan:=zhuan;

          jiaru(nzhuan,zhi);
        end else if l1=l2 then
        begin
          if l1=1 then
          begin
            pd:=0;
            k:=j+1;
            while pd<>1 do
            begin
              inc(k);
              xx:=zhuan div san[k-1] mod 3;
              if xx=1 then dec(pd);
              if xx=2 then inc(pd);
              if pd=1 then s1:=k;
            end;
            nzhuan:=zhuan-san[j-1]-san[j]-san[s1-1];
            jiaru(nzhuan,zhi);
          end else begin
            pd:=0;
            k:=j;
            while pd<>1 do
            begin
              dec(k);
              xx:=zhuan div san[k-1] mod 3 ;
              if xx=1 then inc(pd);
              if xx=2 then dec(pd);
              if pd=1 then s2:=k;
            end;
            nzhuan:=zhuan-san[j-1]*2-san[j]*2+san[s2-1];
            jiaru(nzhuan,zhi);
          end;
        end else
        begin
          jiaru(zhuan,zhi);
          nzhuan:=zhuan-san[j-1]*l1-san[j]*l2;
          swap(l1,l2);
          nzhuan:=nzhuan+san[j-1]*l1+san[j]*l2;
          jiaru(nzhuan,zhi);
        end;
      end;
      swap(i1,i2);
    end;
    j:=m;
    d[i2]:=0;
    for ii:=1 to d[i1] do
    begin
      if (dz[ii,i1]div san[j]) >0then
      begin
        writeln('nimeia');
        continue;
      end;
      inc(d[i2]);
      dz[d[i2],i2]:=dz[ii,i1]*3;
      dui[d[i2],i2]:=dui[ii,i1];

    end;
    swap(i1,i2);
  end;
  if d[i1]<>1 then writeln('0')else
  writeln(dui[1,i1]);
end.

I got WA...could you help me?
I hadn't check the testdata 12*12 empty grid...my code is ok...but I still stoped at test18...

Edited by author 10.07.2010 12:48

???

Edited by author 14.03.2011 04:51