题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1010
题意就是小狗在迷宫迷路.判断小狗能否在指定t时间.刚好到达指定地点.
由于是判断是否存在的问题.我才用了dfs深度遍历.
AC代码:
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;
#define Size 6
/*小狗要在指定的时间t刚好到达指定位置.且不能重复走.所以肯定要定义visit访问. */int dir[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int visit[Size][Size];
char world[Size][Size];
int m, n, T;
char cr;
//开始坐标和终点坐标.
int sx, sy;
int rx, ry;bool dfs(int x,int y, int t)
{//当有路径在指定时间到达门口时.才返回true.if (x == sx && y == sy && t == T){return true;}//减枝1.如果时间到了t.却没有返回,直接返回false.if (t >= T)return false;//减枝2.剩余的时间小于最短距离.if (T - t < abs(x - sx) + abs(y - sy))return false;//减枝3 //这个减枝是最重要的.奇偶减枝.if ((T - t - (abs(x - sx) + abs(y - sy))) %2 != 0)return false;//四个方向的深度遍历.for (int i = 0; i < 4; ++i){int dx = x + dir[i][0];int dy = y + dir[i][1];if (dx >= 0 && dy >= 0 && dx < m && dy < n && visit[dx][dy] == 0 && world[dx][dy] != 'X'){//修改访问权限.visit[dx][dy] = 1;if (dfs(dx, dy, t + 1))return true;//回溯访问权限.visit[dx][dy] = 0;}}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);while (1){cin >> m >> n >> T;memset(visit,0,sizeof(visit));memset(world,0,sizeof(world));if (m == 0 && n == 0 && T == 0)break;for (int i = 0; i < m; ++i){for (int j = 0; j < n; ++j){cin >> cr;if (cr == 'S'){rx = i;ry = j;}else if (cr == 'D'){sx = i;sy = j;}world[i][j] = cr;}}visit[rx][ry] = 1;if (dfs(rx, ry, 0)){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
}