2015
07-25

# 剑侠情缘

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N, M <= 477
3. Mi只包含‘1’-‘9’的数字

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N, M <= 477
3. Mi只包含‘1’-‘9’的数字

3
2 2
11
11
2 2
13
31
3 3
122
231
211

Case 1: 4
Case 2: 0
Case 3: 12

Hint



dp[x][y][i] = ( dp[x][y][i] + dp[x+1][y][j] ) % mod;

dp[x][y][i] = ( dp[x][y][i] + dp[x][y+1][j] ) % mod;

j为相邻格子的能量值，由于人和剑交替补充，对j取反为11-j，又当前格子本身有差值a[x][y]，

int dx[] = {1,0,1,0};//up Right down Left
int dy[] = {0,1,0,-1};

const int M = 480, N = 11, mod = 1000000007;
char s[M];
int a[M][M], n, m, ans;
int dp[M][M][N];

int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif

int T; scanf("%d", &T);
FOE(t, 1, T){
ans = 0;
memset(dp, 0, sizeof dp);
scanf("%d%d", &n, &m);
FOR(x, 0, n) {
scanf("%s", s);
FOR(y, 0, m) a[x][y] = s[y]-'0';
}

FOD(x, n-1, 0) {
FOD(y, m-1, 0) {
int v = a[x][y];
FOR(i, 0, N) {
FOR(r, 0, 2) {
int xx=x+dx[r], yy=y+dy[r];
if(xx>=n || yy>=m) continue;

int temp = (11-i+v) % 11;
dp[x][y][i] = (dp[x][y][i] + dp[xx][yy][temp]) % mod;
}
}
dp[x][y][v]++;
ans = ( ans + dp[x][y][0] ) % mod;
}
}
printf("Case %d: %d\n", t, ans);
}
return 0;
}