미로 탈출(BFS/DFS)

탈출 시간 제한:1000/1000 MS(Java/Others)메모리 제한:32768/32768 K(Java/Others)총 제출(s):37226 승인 제출(s):9036
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
미로 문 제 는 bfs 와 dfs bfs 를 이용 한 코드 를 다음 과 같이 고려 할 수 있 습 니 다(hdu 가 통과 한).

#include 
#include
using namespace std;
char s[105][105];
int n, m;
int k, x1, x2, y11, y2;
int vis[105][105];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int flag;
struct node {
	int x, y;
	int cnt;  
};
int bfs()
{
	queue<node>q;
	memset(vis, 0, sizeof(vis));
	node f, t;
	f.x = x1;
	f.y = y11;
	f.cnt = -1;
	q.push(f);
	vis[x1][y11] = 1;
	while (!q.empty())//q        ture，    false
	{
		node h = q.front();
		q.pop();
		if (h.x == x2 && h.y == y2 && h.cnt <= k)
			//flag = true;
			return 1;
		for (int i = 0;i < 4;i++)
		{
			t.x = h.x + dx[i];
			t.y = h.y + dy[i];
			while (t.x >= 1 && t.x <= n && t.y >= 1 && t.y <= m && s[t.x][t.y] == '.')
			{
				if (vis[t.x][t.y] == 0)
				{
                    t.cnt = h.cnt + 1;
                    vis[t.x][t.y] = 1;
					q.push(t);
					
				}
				node t2;
				t2.x = t.x + dx[i];
				t2.y = t.y + dy[i];
				t = t2;
			}
		}
	}
	return 0;
}
int main()
{
	int t;
	scanf_s("%d", &t);
	while (t--)
	{
		flag = 0;
		scanf_s("%d %d", &n, &m);
		for(int i=1;i<=n;i++)
			for (int j = 1;j <= m;j++)
			{
				cin >> s[i][j];
				
			}
		scanf_s("%d %d %d %d %d", &k, &y11, &x1, &y2, &x2);
		flag = bfs();
		if (flag)
			printf("yes
");
		else
			printf("no
");
	}
	return 0;
}

DFS    ：

```c
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Max 0x3f3f3f

using namespace std;
char map[110][110];
int turn[110][110];
int n, m, x2, y2, ok, k;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
void dfs(int x, int y, int dir)
{
	int i, xx, yy;
	if (x == x2 && y == y2 && turn[x][y] <= k)		
	{
		ok = 1;
		return;
	}
	if (turn[x][y] > k)			
		return;

	if (x != x2 && y != y2 && turn[x][y] == k)			
		return;
	for (i = 0;i < 4;i++)
	{
		xx = x + dx[i];
		yy = y + dy[i];
		if (xx <= 0 || yy <= 0 || xx > m || yy > n || map[xx][yy] == '*')
			continue;
		if (turn[xx][yy] < turn[x][y])		
			continue;
		
		if (dir != -1 && i != dir && turn[xx][yy] < turn[x][y] + 1)
			continue;		
		if (dir != -1 && i != dir)
			turn[xx][yy] = turn[x][y] + 1;
		else
			turn[xx][yy] = turn[x][y];
		map[xx][yy] = '*';		
		dfs(xx, yy, i);
		map[xx][yy] = '.';		
		if (ok)
			return;
	}

}



int main()
{
	int i, j, t, x1, y11;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &m, &n);
		for (i = 1;i <= m;i++)
			for (j = 1;j <= n;j++)
				scanf(" %c", &map[i][j]);
		scanf("%d%d%d%d%d", &k, &y11, &x1, &y2, &x2);		
		memset(turn, Max, sizeof(turn));			
		ok = 0;
		turn[x1][y11] = 0;
		dfs(x1, y11, -1);
		if (ok)
			printf("yes
");
		else
			printf("no
");
	}
	return 0;
}

자세 한 내용 은 참고 하 시 오
Jonariguez