#include #include #include #include #include #include #include #include #define LL long long #define REP(i, n) for(int i = 0;i < (int)(n);i++) #define ALL(x) (x).begin(),(x).end() using namespace std; struct P{ int x,y; P(){} }; struct Node{ int next,prev,cost; Node(int n,int p,int c){ next = n; prev = p; cost = c; } }; int DY[4] = {-1,0,1,0}; int DX[4] = {0,1,0,-1}; int H,W,M; vector

pos; vector field; int con[50][50]; int on[50][50]; int off[50][50]; int trace[50][50]; bool isValid(int x,int y){ return x>=0 && y>=0 && x q;q.push(Node(s.y*W+s.x,-2,0)); while(!q.empty()){ Node n = q.front();q.pop(); int cy = n.next/W; int cx = n.next%W; if(trace[cy][cx]!=-1)continue; trace[cy][cx] = n.prev; if(cx==e.x && cy==e.y)return n.cost; REP(i,4){ int ny = cy+DY[i]; int nx = cx+DX[i]; if(isValid(nx,ny)){ if(field[ny][nx]=='#')continue; q.push(Node(ny*W+nx,n.next,n.cost+1)); } } } } vector visited[50][50]; void add(P e,int &now){ int nx = e.x,ny = e.y; vector tmp; while(true){ tmp.push_back(ny*W+nx); int prev = trace[ny][nx]; if(prev==-2)break; ny = prev/W; nx = prev%W; } REP(i,tmp.size()-1){ int t = tmp[tmp.size()-1-i]; visited[t/W][t%W].push_back(now++); } } int calcDP(int x,int y){ const vector &visit = visited[y][x]; if(visit.size()==0)return 0; int n = visit.size(); vector > dp(n+1,vector(2)); int conCost = con[y][x]; int onCost = on[y][x]; int offCost = off[y][x]; dp[0][0] = onCost+offCost; dp[0][1] = onCost; for(int i=1 ; i