最后一个点T,求dalao帮忙卡个常QAQ
#include<bits/stdc++.h>
#define LL long long
#define _ 0
using namespace std;
/*Grievous Lady*/
template <typename _n_> void mian(_n_ & _x_){
_x_ = 0;int _m_ = 1;char buf_ = getchar();
while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
// #define int long long
#define mod 20110520
int r , c , endx , endy , mp[110][110] , tmp[110][110];
char chino;
unordered_map<int , LL> dp[2];
inline int oqs(int x , int y){
return x << (y << 1);
}
#define add(x , val) \
{ \
x %= mod; (x += val) %= mod; \
}
inline int DP(){
int tmp = (1 << ((c + 1) << 1)) - 1;
LL numnow = 0 , numnxt = 1 , ans = 0;
dp[numnow][0] = 1;
for(int i = 1;i <= r;i ++){
for(int j = 1;j <= c;j ++){
// cout << ans << '\n';
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
int S = k -> first , val = k -> second;
int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
if(!mp[i][j]){
if(!L && !R) add(dp[numnxt][S] , val);
continue;
}
if(!L && !R){
if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(1 , j)] , val);
if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(1 , j - 1)] , val);
if(mp[i][j + 1] && mp[i + 1][j]) add(dp[numnxt][S ^ oqs(2 , j) ^ oqs(2 , j - 1)] , val);
}
if(L && !R){
if(L == 1 && R == 0){
if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(1 , j)] , val);
if(mp[i + 1][j] && L == 1) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(2 , j - 1)] , val);
}
if(L == 2 && R == 0){
add(dp[numnxt][S ^ oqs(L , j - 1)] , val);
if(mp[i][j + 1]) add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(2 , j)] , val);
}
}
if(!L && R){
if(L == 0 && R == 1){
if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] , val);
if(mp[i][j + 1] && R == 1) add(dp[numnxt][S ^ oqs(R , j) ^ oqs(2 , j)] , val);
}
if(L == 0 && R == 2){
add(dp[numnxt][S ^ oqs(R , j)] , val);
if(mp[i + 1][j]) add(dp[numnxt][S ^ oqs(R , j - 1) ^ oqs(R , j)] , val);
}
}
if(L == 1 && R == 1){
add(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] , val);
}
if(i == endx && j == endy){
if(L == 1 && R == 1) add(ans , val);
if(L == 0 && R == 2) add(ans , val);
if(L == 2 && R == 0) add(ans , val);
// return val;
}
}
swap(numnow , numnxt);
}
dp[numnxt].clear();
for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
add(dp[numnxt][(k -> first << 2) & tmp] , k -> second);
}
swap(numnow , numnxt);
}
return ans;
}
inline int Ame_(){
mian(r) , mian(c);
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++){
cin >> chino;
if(chino == '*') mp[i][j] = 0;
else if(chino == '_') mp[i][j] = 1 , endx = i , endy = j;
}
if(r < c){
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
tmp[j][i] = mp[i][j];
swap(r , c);
memset(mp , 0 , sizeof(mp));
for(int i = 1;i <= r;i ++)
for(int j = 1;j <= c;j ++)
mp[i][j] = tmp[i][j];
swap(endx , endy);
}
printf("%lld\n" , DP());
return ~~(0^_^0);
}
int Ame__ = Ame_();
signed main(){;}
/*
3 3
___
_*_
___
*/