「BJOI2016」空袭 - 高维Dp

题目大意

    空袭，又名空中打击，是在复杂地形中常见的一种远距支援打击手段。通常由侦察兵对目标进行指示，之后最近的友方空中支援机将会发射一枚导弹打击目标。
    空袭拥有灵活性强，杀伤力大，丢失率严重等特点。
    导弹从发射到命中需要一定的时间，因此对于移动单位而言打中非常困难。因此，有经验的友军空中支援部队将会预判目标单位的移动方式，并对估计到达时的位置(而不是目标的当前位置)进行打击。
    现在我军侦察兵GloryKen正在练习如何空袭打击一只“嗜血猎食者”（又称“三级狗”）。
    这种敌方单位移动速度快且不规律，通常是侦察兵的天敌，但空袭只需一发即可消灭一只“三级狗”。
    地形可以看作是N×M的网格，有些格子有障碍无法通行。在空地上有一个敌方单位“三级狗”。
    在接下来的一段时间内，侦察兵GloryKen将会对它进行若干次空袭。具体过程可以按回合制来描述。
    三级狗的初始位置在坐标$(x,y)$，面向上下左右的某个方向。
    每个回合由如下几个阶段组成。

1. GloryKen发出一次“空袭指示”，友军空中支援部队立即发射一枚导弹。这颗导弹将会在$a_i$个回合之后命中三级狗当前位置前方$a_i$格的格子（这里的“前方”是指三级狗当前面向的方向。）。如果这个位置在地图外，那么此次空袭失效。
2. 三级狗进行一次“移动”。它可以向上下左右移动一格（不能越界，也不能到达有障碍存在的格子），也可以选择呆在当前的格子。如果进行移动，它的朝向将会变为移动的方向，否则它的朝向不变。
3. 之前所有预定于该回合到达的导弹全部同时到达在预定的位置，如果三级狗被导弹命中，它将立即死亡。导弹不会对地形造成影响，即不会破坏障碍，也不会制造障碍。

    现在，GloryKen想知道，$T$个回合的空袭之后，如果这只三级狗还存活，它的位置可能在哪里。于是，你需要求出，对于每一个格子，这只三级狗有多少种方案能够在第$T$回合恰好到达这个格子，并且存活。两个方案不同，当且
仅当某个回合三级狗的移动选择不同。

---

题目分析

只会写搜索，暴力出奇迹。（比范围多了5分）

考虑，搜索中每个状态可以由$t$（回合），$(x,y)$（坐标），$d$（方向），$\cdots$（各种炸弹状态）来唯一表示。

但这样每个状态量太大了，所以超时。
注意分析题目导弹的攻击方式，当且仅当三级狗在直线移动过程中原地踏步了恰好一次，才可能炸到该三级狗，每次转弯导弹全部失效。

将转弯与原地踏步视为特殊事件，故只有在上一次特殊事件与上上次特殊事件之间的导弹才可能炸到三级狗。
因此强行将特殊事件压入状态。

设$f(t,x,y,d,s1,s2)$表示$\cdots$时，上一个特殊事件与当前坐标直线距离为$s1$，上上个特殊事件到上个特殊事件的直线距离为$s2$（$s2$设为相对距离可以防止玄学错误）时的合法方案数。

那么就很好转移了。

注意在每次转弯后$s2$是没有意义的，故此时不应该有导弹炸到三级狗，需要压入一个$t1$特判一下。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxt=55,maxn=25,mod=1e9+7,dx[4]= {1,0,-1,0},dy[4]= {0,1,0,-1};

int n,m,T,a[maxt],F[maxt][maxn][maxn][4][13][2][13];
bool map[maxn][maxn],vst[maxt][maxn][maxn][4][13][2][13];

struct Node {
	int t,x,y,d,s1,t1,s2;
	Node(int t=0,int x=0,int y=0,int d=0,int s1=0,int t1=0,int s2=0):t(t),x(x),y(y),d(d),s1(s1),t1(t1),s2(s2) {}
} st;

#define f(X) F[X.t][X.x][X.y][X.d][X.s1][X.t1][X.s2]
#define v(X) vst[X.t][X.x][X.y][X.d][X.s1][X.t1][X.s2]

bool Check(Node x) {
	if(x.t>T)return false;
	if(x.t1==1)return true;
	for(int i=x.s1; i<=x.s1+x.s2; i++)if(a[x.t-i]==i)return false;
	return true;
}

void Bfs(Node st) {
	queue<Node> Q;
	Q.push(st);
	f(st)=v(st)=1;
	while(!Q.empty()) {
		Node Now=Q.front();
		Q.pop();
		Node Next=Node(Now.t+1,Now.x,Now.y,Now.d,0,0,Now.s1);
		if(Check(Next)) {
			f(Next)=(f(Next)+f(Now))%mod;
			if(!v(Next)) {
				v(Next)=1;
				Q.push(Next);
			}
		}
		for(int d=0; d<4; d++) {
			Node Next=Node(Now.t+1,Now.x+dx[d],Now.y+dy[d],d);
			if(map[Next.x][Next.y]==0)continue;
			if(d==Now.d)Next.s1=min(Now.s1+1,12),Next.t1=Now.t1,Next.s2=min(Now.s2,12-Next.s1);
			else Next.s1=0,Next.t1=1;
			if(!Check(Next))continue;
			f(Next)=(f(Next)+f(Now))%mod;
			if(!v(Next)) {
				v(Next)=1;
				Q.push(Next);
			}
		}
	}
}

int main() {
	n=Get_Int();
	m=Get_Int();
	T=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			char ch=' ';
			while(!isdigit(ch)&&ch!='.'&&ch!='*')ch=getchar();
			if(isdigit(ch)) {
				map[i][j]=1;
				st=Node(0,i,j,ch-'0',0,1,0);
			} else if(ch=='.')map[i][j]=1;
		}
	for(int i=1; i<T; i++)a[i]=Get_Int();
	a[T]=INT_MAX/2;
	Bfs(st);
	for(int x=1; x<=n; x++) {
		for(int y=1; y<=m; y++) {
			int sum=0;
			for(int d=0; d<4; d++)
				for(int s1=0; s1<=12; s1++)
					for(int t1=0; t1<=1; t1++)
						for(int s2=0; s2<=12; s2++)sum=(sum+F[T][x][y][d][s1][t1][s2])%mod;
			printf("%d ",sum);
		}
		putchar('\n');
	}
	return 0;
}