题目链接：传送门

Problem Description

破解字迷之后，你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石，并离开展馆。整个展馆呈矩形分布，划分为N*M个区域，有唯一的入口和出口（不能从出口进入，同样不能从入口出去）。由某个区域可直接移动至相邻四个区域中的一个，且最快需要一分钟。假设Kid进入放有宝石的区域即可盗取宝石，无需耗时。问至少要封锁几个区域（可以封锁放有宝石的区域，但不能封锁入口和出口）才能保证Kid无法完成任务。

Input

输入的第一行有一个整数C，代表有C组测试数据。每组测试数据的第一行有三个整数N，M，T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图，其中包括：

'S'：入口
'E'：出口
'J'：放有宝石的区域，至少出现一次
'.'：空白区域
'#'：墙

Output

对每组测试数据，输出至少要封锁的区域数。

Sample Input

2
5 5 5
SJJJJ
..##J
.JJJJ
.J...
EJ...
5 5 6
SJJJJ
..##J
.JJJJ
.J...
EJ...

Sample Output

0
2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
char m[10][10];
int w[10][10][2];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int x,y,t;
int x1,y1;
int x2,y2;
struct pos
{
    int x;
    int y;
    int z;
    int time;
};
bool bfs()
{
    int a,b,c,d,e;
    queue<pos>s;
    pos st,ed;
    memset(w,0,sizeof(w));
    st.x=x1;
    st.y=y1;
    st.z=0;
    st.time=-1;
    s.push(st);
    while(!s.empty())
    {
        ed=s.front();
        s.pop();
        if(ed.time<t)
        {
            if(ed.x==x2&&ed.y==y2&&w[ed.x][ed.y][1])
            {
                return false;
            }
        }
        if(ed.time==t)
            continue;
        for(int i = 0; i < 4; i++)
        {
            a=ed.x+dir[i][0];
            b=ed.y+dir[i][1];
            c=ed.time+1;
            if(a<0||a>=x||b<0||b>=y||m[a][b]=='#') continue;
            if(m[a][b] == 'J')
            {
                st.z=1;
            }
            else
            {
                st.z=ed.z;
            }
            if(w[a][b][st.z]==0)
            {
                st.x=a;st.y=b;st.time=c;
                w[a][b][st.z]=1;
                s.push(st);
            }
        }
    }
    return true;
}
bool dfs(int t)
{
    if(!t)
        return bfs();
    for(int i=0;i<x;i++)
        for(int j=0;j<y;j++)
        {
            if(m[i][j]=='S'||m[i][j]=='#'||m[i][j]=='E')
                continue;
            char ch=m[i][j];
            m[i][j]='#';
            if(dfs(t-1))
                return true;
            m[i][j]=ch;
        }
    return false;
}
int main()
{
    int a,b,c;
    cin>>a;
    while(a--)
    {
        cin>>x>>y>>t;
        for(b=0;b<x;b++)
        {
            cin>>m[b];
            for(c=0;c<y;c++)
            {
                if(m[b][c]=='S')
                {
                    x1=b;
                    y1=c;
                }
                if(m[b][c]=='E')
                {
                    x2=b;
                    y2=c;
                }
            }
        }
        if(bfs())
        {
            cout<<"0"<<endl;
        }
        else
        {
            int ss=0;
            for(c=1;c<4;c++)
            {
                if(dfs(c))
                {
                    cout<<c<<endl;
                    ss=1;
                    break;
                }
            }
            if(ss==0)
                cout<<"4"<<endl;
        }
    }
}