미로 탈출 (hdu 1728) (bfs + 기술)

미궁 을 벗어나다
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 33379    Accepted Submission(s): 8140
Problem Description
주어진 m× n (m 행, n 열) 의 미로, 미로 에는 두 개의 위치 가 있 습 니 다. gloria 는 미궁의 한 위치 에서 다른 위치 로 가 고 싶 습 니 다. 물론 미로 중 일 부 는 공 터 이 고 gloria 는 통과 할 수 있 습 니 다. 어떤 곳 은 장애 입 니 다. 그녀 는 돌아 가 야 합 니 다. 미궁의 한 위치 에서 그 와 인접 한 4 개의 위치 까지 만 갈 수 있 습 니 다. 물론 걷 는 과정 에서 gloria 는 미로 밖으로 나 갈 수 없습니다.골 치 아 픈 것 은 글로 리 아 는 방향 감각 이 별로 없 는 사람 이기 때문에 그녀 는 걷 는 과정 에서 너무 많이 구 부 러 져 서 는 안 된다. 그렇지 않 으 면 그녀 는 쓰 러 질 것 이다.우 리 는 주어진 두 위치 가 모두 공 터 라 고 가정 합 니 다. 처음에 gloria 가 향 하 는 방향 은 정 해 지지 않 았 습 니 다. 그녀 는 네 방향 중 하 나 를 선택 하여 출발 할 수 있 습 니 다. 한 번 의 커 브 가 아 닙 니 다.글로 리 아 는 한 자리 에서 다른 자리 로 갈 수 있 을까요?
Input
첫 번 째 행 위 는 하나의 정수 t (1 ≤ t ≤ 100) 로 테스트 데이터 의 개 수 를 나타 내 고 그 다음은 t 조 테스트 데이터 이다. 각 조 테스트 데이터 에서 첫 번 째 행 위 는 두 개의 정수 m, n (1 ≤ m, n ≤ 100) 으로 각각 미궁의 줄 수 와 열 수 를 나타 내 고 그 다음 m 행 은 n 개의 문 자 를 포함 하 며 그 중에서 문자 '는 이 위 치 를 공 터 로 표시 하고 문자' * '는 이 위 치 를 장애 로 표시 한다.입력 데이터 에는 이 두 가지 문자 만 있 습 니 다. 각 그룹 테스트 데이터 의 마지막 행동 은 5 개의 정수 k, x1, y1, x2, y2 입 니 다. (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m), 그 중에서 k 는 gloria 가 가장 많이 돌 수 있 는 커 브 수 를 나타 내 고 (x1, y1), (x2, y2) 는 두 개의 위 치 를 나타 내 며 그 중에서 x1, x2 대응 열, y1, y2 대응 행 을 나타 낸다.
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
Source
"왕 신 은 보 배" 항주 전자 과학기술 대학 프로 그래 밍 초청 경기
커 브 를 특별히 처리 하 세 요. 방법 은 더 이상 갈 수 없 을 때 까지 커 브 횟수 + 1 입 니 다.

#include
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int vis[105][105];
char g[105][105];
int x,y,a,b,k,n,m;
struct node
{
    int x,y,k;
};
queueq;
void bfs()
{
    int flag=1;
    while(!q.empty())
    {
        node t=q.front();
        q.pop();
        if(t.x==x&&t.y==y&&t.k<=k)
        {
            flag=0;
            break;
        }
        node p;
        p.k=t.k+1;//   
        for(int i=0;i<4;i++)
        {
            int newx=t.x+dir[i][0];
            int newy=t.y+dir[i][1];
            while(newx>=0&&newx=0&&newy