题目描述: 寻宝
有这么一块神奇的矩形土地, 为什么神奇呢? 因为上面藏有很多的宝藏该土地由 N*M 个小正方形土地格子组成, 每个小正方形土地格子上, 如果标有 E, 则表示该格可以通过; 如果标有 X, 则表示该格不能通过现在你处于其中的一格上, 用 P 表示, 你只能向与你所在格子相邻的上下左右四个方向移动, 当然如果你即将移向的格子上标有 X, 则不能通过现在的任务是: 如果你能从起点通过每个用 E 标示的格子一次且仅一次, 则你将寻宝成功, 否则则失败
输入
输入包括如下几部分 第一部分: 输入两个数 N(1<=N<=6) 和 M(1<=M<=6), 分别表示该土地的行和列 第二部分: 输入一个只能由 PXE 构成的 N*M 大小的矩阵, 且 P 只能出现一次, 代表你当前所在位置
输出
如果能寻宝成功, 输出 YES; 否则输出 NO
样例输入
- 2 2
- PE
- ES
- 4 4
- PXEE
- EXEE
- EEEE
- EEEE
样例输出
NO
YES
思路: 简单的 DFS
- #include < iostream > #include < cstring > using namespace std;
- int dis[4][2] = { - 1,
- 0,
- 0,
- -1,
- 1,
- 0,
- 0,
- 1
- },
- vis[10][10];
- char map[10][10];
- int n,
- m,
- sum,
- flag;
- void init() {
- memset(vis, 0, sizeof(vis));
- memset(map, \0, sizeof(map));
- sum = flag = 0;
- }
- void dfs(int x, int y, int cnt) {
- if (cnt == sum) {
- flag = 1;
- return;
- }
- if (flag) return;
- int i,
- tx,
- ty;
- for (i = 0; i < 4; i++) {
- tx = x + dis[i][0];
- ty = y + dis[i][1];
- if (tx >= 0 && ty >= 0 && tx < n && ty < m && map[tx][ty] != X && !vis[tx][ty]) {
- vis[tx][ty] = 1;
- dfs(tx, ty, cnt + 1);
- vis[tx][ty] = 0;
- }
- }
- }
- int main() {
- int i,
- j;
- while (cin >> n >> m) {
- init();
- for (i = 0; i < n; i++) cin >> map[i];
- int tx,
- ty;
- for (i = 0; i < n; i++) {
- for (j = 0; j < m; j++) {
- if (map[i][j] == P) tx = i,
- ty = j;
- else if (map[i][j] == E) sum++;
- }
- }
- vis[tx][ty] = 1;
- dfs(tx, ty, 0);
- if (flag) cout << "YES" << endl;
- else cout << "NO" << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2522652.html