hdoj 1983 Kaitou Kid - The Phantom Thief (2) (dfs+bfs)

【題目大意】:キッドが展示開始後T分以内に少なくとも1つの宝石を盗み、パビリオンを離れることを知っています.パビリオン全体が矩形に分布し、N*Mのエリアに分けられ、唯一の入り口と出口があります(出口から入ることはできません.入口から出ることもできません).あるエリアから隣接する4つのエリアの1つに直接移動することができ、最速で1分かかります.Kidが宝石が入ったエリアに入ると宝石を盗むことができ、時間がかかりません.少なくともいくつかのエリアを封鎖してください.(宝石が入ったエリアは封鎖できますが、入り口や出口は封鎖できません)Kidが任務を遂行できないことを保証します.
【解題の考え方】:実は問題を読み終わったら、最悪の場合、出口と入り口付近の非「#」の領域をすぐに閉鎖する必要があることが明らかになった.言い換えれば、最悪の場合、4つの領域を封鎖することはできない.
したがって、現在必要なブラックアウト領域の最小値は、出入り口と、領域をブラックアウトしない場合に実行可能な経路があるかどうかによって得られることを考慮してもよい.
その後,dfsにより現在の最小領域ブラックアウト値より小さい点を列挙し,bfsにより最短ループ検証即刻を求めた.
お父さんのこと...午後は無限次waに貢献しました...现実はp.xをpにたたき、xの后でminに行く时意外にもmin関数を书くことを忘れたことを発见します....==本当に帝王切開して天下に感謝すべきです!!!
【コード】:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <cctype>
#include <map>
#include <iomanip>
                   
using namespace std;
                   
#define eps 1e-8
#define pi acos(-1.0)
#define inf 1<<30
#define pb push_back
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define lowbit(x) (x & (-x))
#define ll long long

int tx[4]={-1,1,0,0};
int ty[4]={0,0,-1,1};
int x,y,minn,t,xx,yy,n,m;
int vis[10][10][2];
char ch[10][10];
bool flag1;
char tmp[5];

struct Node{
    int x,y,cnt,flag;
    Node() {}
    Node(int a,int b,int c,int d){
        x=a,y=b,cnt=c,flag=d;
    }
};

bool check(int x,int y){
    if (x>=0 && x<n && y>=0 && y<m) return true;
    else return false;
}

bool solve_bfs(){
    queue<Node> que;
    que.push(Node(x,y,0,0));
    memset(vis,0,sizeof(vis));
    vis[x][y][0]=1;
    while (!que.empty()){
        Node q;
        q=que.front();
        que.pop();
        for (int i=0; i<4; i++){
            Node p;
            p.x=q.x+tx[i];
            p.y=q.y+ty[i];
            p.cnt=q.cnt+1;
            p.flag=q.flag;
            if (check(p.x,p.y) && ch[p.x][p.y]!='#'){
                if (ch[p.x][p.y]=='E' && p.flag==1) return true;
                if (ch[p.x][p.y]=='J') p.flag=1;
                if (p.cnt<t && vis[p.x][p.y][p.flag]==0){
                    vis[p.x][p.y][p.flag]=1;
                    que.push(p);
                } 
            }
        }
    }
    return false;    
}

int solve_min(){
    int nx,ny,min1=0,min2=0;
    for (int i=0; i<4; i++){
        nx=x+tx[i];
        ny=y+ty[i];
        if (check(nx,ny) && (ch[nx][ny]=='.' || ch[nx][ny]=='J'))
           min1++; 
    }
    for (int i=0; i<4; i++){
        nx=xx+tx[i];
        ny=yy+ty[i];
        if (check(nx,ny) && (ch[nx][ny]=='.' || ch[nx][ny]=='J'))
           min2++; 
    }
    return min(min1,min2);
}

void solve_dfs(int count,int now){
    if (count<minn){
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++){                
                if (ch[i][j]=='.' || ch[i][j]=='J'){
                    tmp[now]=ch[i][j];
                    ch[i][j]='#';
                    if (now==count) if (!solve_bfs()) {minn=min(count,minn); flag1=true; return ;}
                    if (flag1) return ;
                    if (now<count) solve_dfs(count,now+1);
                    ch[i][j]=tmp[now];                    
                }
            }
    }
    else return ;
}

int main() {
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d%d",&n,&m,&t);
        getchar();
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                scanf("%c",&ch[i][j]);
                if (ch[i][j]=='S') x=i,y=j;
                if (ch[i][j]=='E') xx=i,yy=j;
            }
            getchar();
        }
        minn=solve_min();
        if (!solve_bfs()) minn=0;
        flag1=false;
        solve_dfs(1,1);
        flag1=false;
        solve_dfs(2,1);
        flag1=false;
        solve_dfs(3,1);
        printf("%d
",minn);  
    }
    return 0;
}