タイトル1672:迷宮問題【データ構造】

タイトルの出所:C言語網Look!I’m back.I have watch ed may foreign Serious.That’s really make a big difference for me~
テーマの説明
明さんは迷路にいます.出発点から終点までの最短距離を探してください.明さんは上下左右の四つの方向にしか動かないです.
入力
複数のグループのテストデータを入力します.入力の最初の行は整数Tで、Tグループのテストデータがあることを表しています.各グループの入力の最初の行は2つの整数NとM(1<=N,M<=100)である.次のN行には、各行にM文字が入力され、各文字は迷路の中の小さい四角形を表します.文字の意味は以下の通りです.「S」:起点「E」:終点「-」:空き地は、「胪」を通じてできます.障害は、データを入力することによって保証できず、スタートとゴールしかないです.
出力
各グループの入力に対して、起点から終点までの最短距離を出力します.起点から終点までの道がなければ、-1を出力します.
サンプル入力

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

サンプル出力
9
コードAND Analysis
First、it is a grapph trversal and use the Depth First Traversal algorithm.For the dfs function、there are many probles which are really hidden.DFS考え方は、現在位置の合法性を判断する2、遍歴を続ける必要があるかどうかを判断することです.現在の位置が終点位置かどうかを判断します.終点ではなく、現在の位置の上、下、左、右を巡回します.
関連する操作問題:

第2と第3のステップを組み合わせて、最終記録の終了位置を保証するステップ数は最も少ない.

による次のステップの走向は、それぞれx方向とy方向の循環の2つの層の循環であるが、両者のうち1つが0であり、1つが0でないことを保証する.これは毎回一歩しか歩けないからです.絶対値で判断できる:(vi[x][y] == 0 || vi[x][y] > step)

は、このステップが重要かもしれません.(場合によっては)まず、キーボードバッファと関数stepIndex = abs(mx) + abs(my); stepIndex == 1の役割を明確にして、文字以外の読み取りを行うと、リターンスペースなどがキーボードバッファに保存されます.このときはfflush(stdin)を使って

を読み取ります.

#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);

	}
}