HDU 1983：Kaitou Kid - The Phantom Thief (2)

Kaitou Kid - The Phantom Thief (2)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1404 Accepted Submission(s): 525
클릭 하여 링크 열기
Problem Description
글자 광 을 풀 고 나 면 키 드 가 전시회 시작 후 T 분 안에 최소한 보석 하 나 를 훔 쳐 전시관 을 떠 날 것 이라는 것 을 알 게 된다.전체 전시관 은 사각형 으로 분포 되 어 있 으 며 N*M 개 구역 으로 나 뉘 어 유일한 입구 와 출구 가 있다(출구 로 들 어 갈 수 없고 마찬가지 로 입구 로 나 갈 수 없다).한 지역 에서 인접 한 네 지역 중 하나 로 직접 이동 할 수 있 고 빠 르 면 1 분 이 걸린다.키 드 가 보석 이 놓 인 구역 에 들 어가 면 보석 을 훔 칠 수 있 으 며,시간 이 걸 리 지 않 습 니 다.--최소한 몇 개의 구역(보석 이 들 어 있 는 구역 은 봉쇄 할 수 있 지만 입구 와 출구 는 봉쇄 할 수 없다)을 봉쇄 해 야 키 드 가 임 무 를 수행 하지 못 할 수 있다 고 보장 할 수 있다.

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 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 10;
char Map[MAXN][MAXN];
int vis[MAXN][MAXN][2];
/**    vis          ，              ，         
 64，     ，     1   1     ，                。    
2      **/
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int C,N,M,T;
int sx,sy,ex,ey;
struct pos
{
    int x;
    int y;
    int flag;  ///                 
    int time;  ///    
};
bool BFS()
{
    queuequ;
    pos now,nex;
    memset(vis,0,sizeof(vis));
    now.x = sx;
    now.y = sy;
    now.flag = 0;
    now.time = 0;
    vis[now.x][now.y][now.flag] = 1;
    qu.push(now);
    while(!qu.empty())
    {
        now = qu.front();
        qu.pop();
        if(now.time <= T)
        {
            if(now.x == ex && now.y == ey && vis[now.x][now.y][1])
                return false;
            if(now.time == T)  
                continue;
        ///     T，     T           ，                
        }
        for(int i = 0; i < 4; i++)
        {
            nex.x = now.x + dir[i][0];
            nex.y = now.y + dir[i][1];
            nex.time = now.time + 1;
            ///    ，    
            if(nex.x<0 || nex.x>=N || nex.y<0 || nex.y>=M) continue;
            if(Map[nex.x][nex.y] == '#') continue;
            if(now.flag == 1 || Map[nex.x][nex.y] == 'J')  
            {
                ///              ，         。  flag   1
                nex.flag = 1;
                if(vis[nex.x][nex.y][nex.flag]==0)
                {
                    vis[nex.x][nex.y][nex.flag] = 1;
                    qu.push(nex);
                }
            }
            else
            {
                nex.flag = now.flag;
                if(vis[nex.x][nex.y][nex.flag]==0)
                {
                    vis[nex.x][nex.y][nex.flag] = 1;
                    qu.push(nex);
                }
            }

        }
    }
    return true;
}
bool dfs(int t)
{
    if(!t) return BFS();
    for(int i=0;i

HDU 1983：Kaitou Kid - The Phantom Thief (2)

좋은 웹페이지 즐겨찾기