UVA 707 – Robbery(内存搜索)

UVA 707 – Robbery(内存搜索)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

UVA 707 - Robbery(内存搜索)此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。

UVA 707 – Robbery

题目链接

题意:在一个w * h的图上。t个时刻,然后知道一些信息,每一个时刻没有小偷的矩阵位置,问哪些时刻能够唯一确定小偷位置。和确定小偷是否已经逃走,假设没逃走。可是也没有时刻能够能够确定小偷位置,就是不知到

思路:记忆化搜索。dp[x][y][ti]表示在x。y位置。ti时刻时候,小偷是否可能出如今这个位置,1表示有可能。0表示没可能,因为小偷一次最多仅仅能上下左右走一步或者不走。所以去dfs一遍就可以

最后推断的时候,假设有一个时刻没有一个1,就表示已经逃走。假设全部时刻的1都超过1个,那么就是不知道。其它就能够确定答案

代码:

#include <cstdio>#include <cstring>#include <vector>using namespace std;const int N = 105;const int d[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};typedef pair<int, int> pii;int w, h, t, n;int dp[N][N][N];vector<pii> ans[N];void init() {	scanf("%d", &n);	int ti, xa, ya, xb, yb;	memset(dp, -1, sizeof(dp));	while (n--) {		scanf("%d%d%d%d%d", &ti, &xa, &ya, &xb, &yb);		for (int i = xa; i <= xb; i++)			for (int j = ya; j <= yb; j++)				dp[i][j][ti] = 0;	}}int dfs(int x, int y, int ti) {	int &ans = dp[x][y][ti];	if (ans != -1) return ans;	ans = 0;	if (ti == t) return ans = 1;	for (int i = 0; i < 5; i++) {		int xx = x + d[i][0];		int yy = y + d[i][1];		if (xx < 1 || xx > w || yy < 1 || yy > h) continue;		if (dfs(xx, yy, ti + 1))			ans = 1;	}	return ans;}int solve() {	int flag;	for (int i = 1; i <= t; i++) {		ans[i].clear();		flag = 0;		for (int j = 1; j <= w; j++)			for (int k = 1; k <= h; k++) {				if (dp[j][k][i] == 1) {					ans[i].push_back(make_pair(j, k));					flag = 1;				}			}		if (flag == 0) return 0;	}	flag = 1;	for (int i = 1; i <= t; i++) {		if (ans[i].size() == 1) {			printf("Time step %d: The robber has been at %d,%d.\n", i, ans[i][0].first, ans[i][0].second);			flag = 0;		}	}	if (flag) return 1;	return 2;}int main() {	int cas = 0;	while (~scanf("%d%d%d", &w, &h, &t) && w) {		init();		for (int i = 1; i <= w; i++)			for (int j = 1; j <= h; j++)				dfs(i, j, 1);		printf("Robbery #%d:\n", ++cas);		int tmp = solve();		if (tmp == 0) printf("The robber has escaped.\n");		else if (tmp == 1) printf("Nothing known.\n");		printf("\n");	}	return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117883.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 常见的ARM集成开发环境

    常见的ARM集成开发环境1.ARMSDT:是ARM公司为方便用户在ARM芯片上进行应用软件开发而推出的一整套开发工具。到ARMSDT2.5.1,ARM宣布推出ARMADS1.0取代了ARMSDT,不再对ARMSDT进行维护。ARMSDT支持的ARM处理器最高到包括ARM9在内的所有ARM处理器。配合Angel驻留程序和JTAG仿真器,用户使用可方便的使用ARMSDT进行应用程序的开发。2.ARM

  • pycharm规范快捷键_pycharm修改快捷键

    pycharm规范快捷键_pycharm修改快捷键在写程序的过程中常常会有代码不整齐不规范的警告这时候用pycharn快速规整代码的快捷键为Ctrl+Alt+L即可解决

  • python和c++哪个好_run pycharm community edition

    python和c++哪个好_run pycharm community edition在pycharm中使用django命令的过程中经常会用到pythonmanage.py相关的命令,每次都输入pythonmanage.py会比较麻烦,可以利用pycharm提供的tools来省去pythonmanage.py的重复输入。具体实现过程如下:先进入settings完成如下操作随后可勾选Tools中的Runmanage.pyTask完成后即可以直接输入manag…

  • 哈希表、哈希冲突

    哈希表、哈希冲突哈希表1.哈希表是一种以键值key存储数据value的结构,以key作为标识值存储value值;只要输入待查找的key,即可获取其对应的value值。当按照键值查询元素时,使用相同的hash函数将key转换为数组下标,从数组中按照下标对应的位置获取数据。它实际上是数组的一种扩展,数组+链表+红黑树。2.哈希表的设计哈希函数的设计首先不能过于复杂,复杂的哈希函数会间接的影响hash表的性能;其次要求哈希值应该尽可能随机且均匀分布,避免或者减少哈希冲突的数量,使每个桶中存储的数据比较平均。常规的设计方法

  • drupal学习教程(待续)「建议收藏」

    drupal学习教程(待续)「建议收藏」1.drupal模块安装a.安装captcha模块–>模块–>用户贡献的模块–>b.启用captcha模块–>模块–>选择–>保存配置c.汉化captcha模块打开https://localize.drupal.org/translate/languages/zh-hans下载captcha汉化包–>配置–>翻译–>导入b.配置capt

  • 详解mysql 主从复制原理

    详解mysql 主从复制原理

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号