HDOJ - 1072 - Nightmare 문제 풀이 보고서

이것 은 매우 풀 만 한 검색 문제 다.제목: 이 그 는 깨 어 나 자신 이 시한폭탄 이 설 치 된 2 차원 미로 에 있다 는 것 을 알 게 되 었 다. 도망 가기 위해 서 는 미로 가 폭발 하기 전에 미 로 를 벗 어 나 야 한다.시한폭탄 의 초기 시간 은 6 분 이 었 다. 이 그 는 1 분 에 상하 좌우 로 한 칸 만 걸 을 수 있 었 고 벽 을 걸 을 수도 없고 경 계 를 통과 할 수도 없 었 다.미궁 에는 시한폭탄 시간 을 리 셋 하 는 장치 가 있어 시한폭탄 의 시간 을 6 분 으로 초기 화 할 수 있 으 며, 현재 칸 에 리 셋 기 가 있 으 면 시한폭탄 을 리 셋 할 수 있다.지도 에서 1 은 벽 을 대표 하고 2 는 출발점 을 대표 하 며 3 은 미로 출구 를 대표 하 며 4 는 이곳 에 리 셋 기 가 있다 는 것 을 의미한다.문 제 는 이 그 가 폭탄 이 터 지기 전에 미 로 를 탈출 할 수 있 느 냐 하 는 것 이다.
       나의 문제 풀이 방향: 먼저 가장 짧 은 시간 을 구하 고 BFS 로 한 다음 에 여기 리 셋 시간 이라는 장치 가 있 습 니 다. 저 는 모든 점 에 남 은 시간 에 변 수 를 설정 하면 한 걸음 걸 을 때마다 변 수 를 줄 이 고 리 셋 장치 에 도착 할 때 남 은 시간 을 6 으로 설정 합 니 다.우 리 는 종점 에 도착 하 는 가장 짧 은 시간 을 요구 하기 때문에 폭탄 은 아직 폭발 하지 않 았 으 면 됩 니 다. 그래서 저 는 vis 배열 로 이 점 에 도착 하 는 가장 짧 은 시간 을 저장 하고 초기 vis 배열 은 모두 - 1 로 설정 합 니 다.또한 리 셋 기 위 치 를 표시 해 야 합 니 다. 사용 한 후에 사용 할 수 없습니다. 그러면 무한 BFS 를 방지 할 수 있 습 니 다.모든 점 에서 현재 시간 이 vis 보다 짧 은 지 판단 합 니 다. 예, vis 를 현재 시간 으로 설정 합 니 다. 물론 vis 가 - 1 이면 바로 값 을 부여 합 니 다.마지막 으로 남 은 시간 이 1 일 때 종점 에 도착 하지 않 았 거나 사용 하지 않 은 리 셋 지점 에 도착 하지 않 았 을 때 우 리 는 계속 검색 하 는 것 을 멈 춰 야 한다. 아무리 다음 단 계 를 걸 어도 폭발 할 것 이기 때문이다.
       다음은 제 문제 풀이 코드 입 니 다. BFS 문제 풀이.

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define N 10

struct point        //      
{
    int x, y;       //  
    int remain;     //      
    int step;       //       ，     
};

int n, m, t;
int map[N][N];
int vis[N][N];      //               
point start, end;   //     
queue  q;

void Read();        //  

void Init();        //   

void DataProcess(); //Bfs  

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        Read();
        Init();
        DataProcess();
    }
    return 0;
}

void Read()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for (i=0; i b.step) vis[b.x][b.y] = b.step;
            q.push(b);
        }
        if (a.x - 1 >= 0 && map[a.x-1][a.y] != 0)
        {
            b = a;
            b.x = a.x - 1;
            b.step++;
            b.remain--;
            if (map[b.x][b.y] == 4 && vis[b.x][b.y] == -1) b.remain = 6;
            if (vis[b.x][b.y] == -1 || vis[b.x][b.y] > b.step) vis[b.x][b.y] = b.step;
            q.push(b);
        }
        if (a.y + 1 < m && map[a.x][a.y+1] != 0)
        {
            b = a;
            b.y = a.y + 1;
            b.step++;
            b.remain--;
            if (map[b.x][b.y] == 4 && vis[b.x][b.y] == -1) b.remain = 6;
            if (vis[b.x][b.y] == -1 || vis[b.x][b.y] > b.step) vis[b.x][b.y] = b.step;
            q.push(b);
        }
        if (a.y - 1 >= 0 && map[a.x][a.y-1] != 0)
        {
            b = a;
            b.y = a.y - 1;
            b.step++;
            b.remain--;
            if (map[b.x][b.y] == 4 && vis[b.x][b.y] == -1) b.remain = 6;
            if (vis[b.x][b.y] == -1 || vis[b.x][b.y] > b.step) vis[b.x][b.y] = b.step;
            q.push(b);
        }
    }
    printf("%d
", vis[end.x][end.y]);      //      vis        
    return;
}