博客

description

给一张个迷宫，问能否从起点走到终点，只能往上下左右走，不能斜着走。

input

多组

测试数据，每组第一行两个正整数，分别为n和m，表示n这个迷宫有n行m列(0<n,m<10)，接着是n行m列。

*#'表示路
'*’表示墙
‘S’表示起点
‘T’表示终点

output

每组测试数据输出一个结果，如果能从S走到T，输出“YES”,否则输出“NO”。

sample input

2 2
S*
#T
3 3
S*#
#*T
##*

sample output

YES
NO

method 1 -> depth first search

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
char maze[15][15];
bool mark[15][15], flag;
int n, m, sx, sy;
void dfs(const int cx, const int cy) {
	mark[cx][cy] = true;
	if (maze[cx][cy] == 'T') {
		flag = true;
		return;
	}
	for (int i = 0; i < 4; ++i) {
		int nx = cx + dir[i][0];
		int ny = cy + dir[i][1];
		if (nx >= 0 && ny >= 0 && nx < n && ny < m && maze[nx][ny] != '*' && !mark[nx][ny])
			dfs(nx, ny);
	}
}
int main(int argc, char **argv) {
	while (~scanf("%d%d", &n, &m)) {
		flag = false;
		memset(mark, false, sizeof mark);
		for (int i = 0; i < n; ++i) {
			scanf("%s", maze[i]);
			for (int j = 0; j < m; ++j)
				if (maze[i][j] == 'S') {
					sx = i;
					sy = j;
				}
		}
		dfs(sx, sy);
		if (flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

method 2 -> breadth first search

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct coordinate {
	int x, y;
} start, endd;
const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool maze[15][15], flag;
int n, m;
void bfs() {
	queue <coordinate> q;
	coordinate t;
	t.x = start.x;
	t.y = start.y;
	q.push(t);
	while (!q.empty()) {
		t = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			coordinate u;
			u.x = t.x + dir[i][0];
			u.y = t.y + dir[i][1];
			if (u.x >= 0 && u.y >= 0 && u.x < n && u.y < m && !maze[u.x][u.y]) {
				q.push(u);
				if (u.x == endd.x && u.y == endd.y) {
					flag = true;
					break;
				}
				maze[u.x][u.y] = true;
			}
		}
		if (flag) break;
	}
	return;
}
int main(int argc, char **argv) {
	while (cin >> n >> m) {
		flag = false; 
		memset(maze, false, sizeof maze);
		for (int i = 0; i < n; ++i) {
			char str[15]; cin >> str;
			for (int j = 0;j < m; ++j)
				if (str[j] == '*') maze[i][j] = true;
				else if (str[j] == 'S') {
					start.x = i;
					start.y = j;
				}
				else if (str[j] == 'T') {
					endd.x = i;
					endd.y = j;
				}
		}
		bfs();
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;			
	}
	return 0;
} 

#include <iostream>
#include <cstring> 
#include <cstdio>
using namespace std;
struct coordinate {
	int x, y;
	bool operator == (const coordinate &r) const {
		if (this->x == r.x && this->y == r.y) return true;
		else return false;
	} 
} sp, ep;
int n, m;
bool maze[15][15], flag;
const int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
void bfs() {
	coordinate q[15 * 15 + 5];
	int tail = 1;
	int head = 0;
	q[tail] = sp;
	maze[sp.x][sp.y] = true;
	while (head < tail) {
		++head;
		for (int i = 0; i < 4; ++i) {
			coordinate u;
			u.x = q[head].x + dir[i][0];
			u.y = q[head].y + dir[i][1];
			if (u.x >= 0 && u.y >= 0 && u.x < n && u.y < m && !maze[u.x][u.y]) {
				++tail;
				q[tail].x = u.x;
				q[tail].y = u.y;
				if (u == ep) {
					flag = true;
					break;
				}
				maze[u.x][u.y] = true;
			}
		}
		if (flag) break;
	}
}
int main(int argc, char **argv) {
	while (cin >> n >> m) {
		flag = false;
		memset(maze, false, sizeof maze);
		for (int i = 0; i < n; ++i) {
			char str[15]; cin >> str;
			for (int j = 0; j < m; ++j)
				if (str[j] == '*') maze[i][j] = true;
				else if (str[j] == 'S') {
					sp.x = i;
					sp.y = j;
				}
				else if (str[j] == 'T') {
					ep.x = i;
					ep.y = j;
				}
		}
		bfs();
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl; 
		
	}
	return 0;
}