hdu 1728 미로 탈출(물 bfs)

미궁 을 벗어나다
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11245    Accepted Submission(s): 2687
Problem Description
주어진 m× n(m 행,n 열)의 미로,미로 에는 두 개의 위치 가 있 습 니 다.gloria 는 미궁의 한 위치 에서 다른 위치 로 가 고 싶 습 니 다.물론 미로 중 일 부 는 공 터 이 고 gloria 는 통과 할 수 있 습 니 다.어떤 곳 은 장애 입 니 다.그녀 는 돌아 가 야 합 니 다.미궁의 한 위치 에서 그 와 인접 한 4 개의 위치 까지 만 갈 수 있 습 니 다.물론 걷 는 과정 에서 gloria 는 미로 밖으로 나 갈 수 없습니다.골 치 아 픈 것 은 글로 리 아 는 방향 감각 이 별로 없 는 사람 이기 때문에 그녀 는 걷 는 과정 에서 너무 많이 구 부 러 져 서 는 안 된다.그렇지 않 으 면 그녀 는 쓰 러 질 것 이다.우 리 는 주어진 두 위치 가 모두 공 터 라 고 가정 합 니 다.처음에 gloria 가 향 하 는 방향 은 정 해 지지 않 았 습 니 다.그녀 는 네 방향 중 하 나 를 선택 하여 출발 할 수 있 습 니 다.한 번 의 커 브 가 아 닙 니 다.글로 리 아 는 한 자리 에서 다른 자리 로 갈 수 있 을까요?
 
Input
제1 행위 1 개 정수 t(1≤t≤100)는 테스트 데이터 의 개 수 를 나타 내 고 다음은 t 조 테스트 데이터 이 며 각 조 테스트 데이터 중,
첫 번 째 행위 의 두 정수 m,n(1≤m,n≤100)은 각각 미궁의 줄 수 와 열 수 를 나타 내 고,다음 m 줄 은 n 개의 문 자 를 포함 하 며,그 중 문자''는 이 위 치 를 공 터 로 표시 하고,문자'*'는 이 위 치 를 장애 로 표시 하 며,입력 데이터 에는 이 두 가지 문자 만 있 으 며,각 조 테스트 데이터 의 마지막 행위 5 개의 정수 k,x
1, y
1, x
2, y
2 (1 ≤ k ≤ 10, 1 ≤ x
1, x
2 ≤ n, 1 ≤ y
1, y
2 ≤m),그 중 k 는 gloria 가 가장 많이 돌 수 있 는 커 브 수 를 나타 낸다.(x
1, y
1), (x
2, y
2)두 자 리 를 나타 내 는 x
1，x
2 대응 열,y
1, y
2 대응 행.
 
Output
각 그룹의 테스트 데 이 터 는 한 줄 로 대응 합 니 다.만약 gloria 가 한 위치 에서 다른 위치 로 갈 수 있다 면"yes"를 출력 합 니 다.그렇지 않 으 면"no"를 출력 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    no
yes
   
   
   
   

제목:미 로 를 하나 주 고 점 을 2 개 주 며 미 로 는 벽 과 공 터 만 있 습 니 다.두 점 사이 의 모든 경로 에서 커 브 횟수 가 가장 적은 횟수 를 구하 고 주어진 k 와 비교 합 니 다.
제목 분석:물 bfs.이상 하 게 도 그 당시 에 오래 써 서 열 몇 번 이나 사 귄 적 이 없어 서 오늘 은 대충 쓰 고 넘 어 갔 어 요............................................
입력 조심 하 세 요.문 제 는 잘 보 세 요.물 문 제 는 하나 입 니 다.
자세 한 내용 은 코드 를 보십시오.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 105;
const int M = 1000005;
const int INF = 0x3f3f3f3f;
char map[N][N];
int step[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
struct node
{
    int x,y,turn;
}lcm[M],ss,now;
int m,n;
int si,sj,ei,ej;
int k;

bool isok(int x,int y)
{
    return (x >= 0 && y >= 0 && x < n && y < m);
}

void bfs()
{
    int head,tail;
    head = tail = 0;
    memset(step,INF,sizeof(step));
    ss.x = si;ss.y = sj;ss.turn = -1;
    step[si][sj] = 0;
    lcm[tail ++] = ss;
    while(head != tail)
    {
        now = lcm[head ++];
        if(head >= M)
            head -= M;
        for(int i = 0;i < 4;i ++)
        {
            ss = now;
            ss.turn ++;
            int tx = ss.x + dx[i];
            int ty = ss.y + dy[i];
            while(isok(tx,ty) && map[tx][ty] != '*')
            {
                if(step[tx][ty] > ss.turn)
                {
                    step[tx][ty] = ss.turn;
                    ss.x = tx;
                    ss.y = ty;
                    lcm[tail ++] = ss;
                    if(tail >= M)
                        tail -= M;
                }
                tx += dx[i];
                ty += dy[i];
            }
        }
    }
    if(step[ei][ej] <= k)
        puts("yes");
    else
        puts("no");
}

int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%d%d",&n,&m);
        for(i = 0;i < n;i ++)
            scanf("%s",map[i]);
        scanf("%d%d%d%d%d",&k,&sj,&si,&ej,&ei);
        si --;sj --;ei --;ej --;
        if(si == ei && sj == ej)
        {
            puts("yes");
            continue;
        }
        bfs();
    }
    return 0;
}
//31MS	424K