제목 1672: 미궁 문제 [데이터 구조]

제목 출처: C 언어 망 룩!I’m back. I have watched many foreign Serious. That’s really make a big difference for me~
제목 설명
샤 오 밍 은 미로 에 있 습 니 다. 샤 오 밍 을 도와 출발점 에서 종점 까지 의 가장 짧 은 길 을 찾 아 주세요.샤 오 밍 은 상하 좌우 네 방향 으로 만 이동 할 수 있다.
입력
여러 그룹의 테스트 데 이 터 를 입력 하 십시오.입력 한 첫 줄 은 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 입 니 다.각 조 가 입력 한 첫 줄 은 두 개의 정수 N 과 M (1 < = N, M < = 100) 이다.다음 N 줄 은 줄 마다 M 개의 문 자 를 입력 하고 모든 문 자 는 미로 의 작은 사각형 을 표시 합 니 다.문자 의 의 미 는 다음 과 같다. 'S': 출발점' E ': 종점' - ': 공 터 는' \ # ': 장 애 를 통 해 입력 데 이 터 를 통 해 있 고 출발점 과 종점 만 보장 할 수 없다.
출력
각 조 의 입력 에 대해 출력 은 출발점 에서 종점 까지 의 가장 짧 은 거리 이 고 출발점 에서 종점 까지 의 길이 존재 하지 않 으 면 출력 - 1.
샘플 입력

1
5 5
S-###
-----
##---
E#---
---##

샘플 출력
9
Code AND Analysis
First, it is a graph traversal and use the Depth First Traversal algorithm. For the dfs function, there are many problems which are really hidden. DFS 사고방식 은 다음 과 같다.바로 현재 위치 가 종점 위치 인지 아 닌 지 를 판단 하 는 것 이다. 4. 종점 이 아니 라 현재 위치의 상, 하, 좌, 우 를 옮 겨 다 니 는 것 이다.
질문
4. 567917. 2 단계 와 3 단 계 를 결합 하여 최종 기록 의 끝 위 치 를 확보 하 는 걸음 수가 가장 적다
4. 567917. 다음 단계 의 방향 은 2 층 순환 을 사용 하 는데 각각 x 와 y 방향의 순환 이지 만 이들 중 하 나 는 0 이 고 하 나 는 0 이 아니 어야 한다.매번 한 걸음 만 걸 을 수 있 기 때 문 이 야!!사실은 절대 치 로 판단 할 수 있다.
4. 567917. 이 단 계 는 중요 할 수 있 습 니 다.

#include
#include

#define MAXN 100
char dg[MAXN + 1][MAXN + 1];
int vi[MAXN + 1][MAXN + 1] = {
      0 };
int stx, sty, endx, endy;

int dfs(int row, int col, int x, int y, int step)
{
     
	//        
	if (x < 0 || y < 0 || x >= row || y >= col || vi[x][y] == -1)	return 0;
	//               
	if (vi[x][y] == 0 || vi[x][y] > step)	vi[x][y] = step;
	else	return 0;
	if (dg[x][y] == 'E') return 0;
	int mx, my;
	for (mx = -1; mx <= 1; mx++) {
     
		for (my = -1; my <= 1; my++) {
     
			//mx my     0    0
			//   0         mx  0
			if ((mx && my) || (mx == 0 && my == 0))	continue;
			dfs(row, col, x + mx, y + my, step + 1);
		}
	}
	return 1;
}
int solve(int row, int col)
{
     
	int ans;
	dfs(row, col, stx, sty, 0);
	ans = vi[endx][endy];
	ans = ans ? ans : -1;
	return ans;
}
int main()
{
     
	int L, i, j, row, col, ans;
	scanf("%d", &L);
	//     
	getchar();
	while (L--) {
     
		memset(vi, 0, sizeof(vi));
		//       
		scanf("%d %d", &row, &col);
		//     
		getchar();
		for (i = 0; i < row; i++) {
     
			for (j = 0; j < col; j++) {
     
				dg[i][j] = getchar();
				if (dg[i][j] == 'S') {
     
					stx = i;	sty = j;
				}
				if (dg[i][j] == 'E') {
     
					endx = i;	endy = j;
				}
				if (dg[i][j] == '#') {
     
					vi[i][j] = -1;
				}
			}
			//     
			getchar();
		}
		ans = solve(row, col);
		printf("%d
", ans);

	}
}