学步园

题意：从起始点经过t步能到达哪些格子，求出所有格子的个数：

思路：1、一步都不能走的时候，为1

2、第n步到达某个格子，则第n+2步也可以到达这里，标记一下，把奇数次偶数次分开就ok了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;
const int N = 109;
char mp[N][N];
int n;
bool oor(int x,int y){
    if(x<0||x>=n) return false;
    if(y<0||y>=n) return false;
    if(mp[x][y]=='#') return false;
    return true;
}
int T,sx,sy;
struct nod{
    int x,y,dis;
};
queue<nod> que;
int dp[N][N][2];
int dx[]={0,0,-1,-1,-1,1,1,1};
int dy[]={-1,1,-1,0,1,-1,0,1};
void solve()
{
    while(!que.empty()) que.pop();
    nod e,t;
    e.x = sx,e.y = sy;e.dis=0;
    memset(dp,0,sizeof(dp));
    dp[sx][sy][0] = 1;
    que.push(e);
    while(!que.empty())
    {
        e = que.front();que.pop();
        if(e.dis>=T) break;
        for(int i=0;i<8;i++)
        {
            int tx = e.x+dx[i],ty=e.y+dy[i],d = e.dis+1;
            if(!oor(tx,ty)) continue;
            if(dp[tx][ty][d%2]) continue;
            dp[tx][ty][d%2] = 1;
            t.x = tx,t.y=ty,t.dis = d;
            que.push(t);
        }
    }
    int tt = T&1,ans=0;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    if(dp[i][j][tt])
    {
        ans++;
    }
    ans = max(ans,1);
    printf("%d\n",ans);
}
int main()
{
   // freopen("in.txt","r",stdin);
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d%d%d",&n,&T,&sx,&sy);
        sx--,sy--;
        for(int i=0;i<n;i++)
        scanf("%s",mp[i]);
        solve();
    }
    return 0;
}