首页 > 其他分享 >UVA10384 推门游戏 The Wall Pushers(IDA_,A_)

UVA10384 推门游戏 The Wall Pushers(IDA_,A_)

时间:2022-10-31 08:56:36浏览次数:426  
标签:yy 推墙 return Wall 网格 UVA10384 int xx IDA

题目大意

给你一个 \(4\times 6\) 的网格图,网格边缘上可能有墙。对于每一个网格有一个权值 \(val\),其中

\[\begin{aligned}val= & & 1(\text{如果这个网格左边缘(西边缘)有墙})\\ & +&2(\text{如果这个网格上边缘(北边缘)有墙})\\&+&4(\text{如果这个网格右边缘(东边缘)有墙})\\&+&8(\text{如果这个网格下边缘(南边缘)有墙})\end{aligned} \]

然后你就可以通过这些网格的权值唯一确定这张网格图了。

然后题目还会给你一个起点坐标 \((st_x,st_y)\)(注意,题目给的 \(st_x\)、\(st_y\) 是反着输入的,即题目给出的顺序为:\(st_y\)、\(st_x\)),然后你从这个起点开始走,每步你可以往上下左右四个方向移动一格,但有限制条件。

具体来讲,假设你当前所在格子为 \((x,y)\),移动方向为 \(dir\) ,下一步移动到的格子为 \((xx,yy)\),那么:

  1. 当 \((x,y)\) 和 \((xx,yy)\) 之间没有墙时,你可以直接移动到 \((xx,yy)\),整个过程算 \(1\) 步 。

  2. 当 \((x,y)\) 和 \((xx,yy)\) 之间有墙时,那么你可以把这堵墙往 \(dir\) 方向推一格,但要保证推到的地方没有墙且在网格图内(含边界),然后再走到 \((xx,yy)\),整个过程算 \(1\) 步,也就是说推墙操作不算入步数。

最后问你离开网格图的最少步数是多少。

样例解释:

一开始:

向上推墙:

向右推墙:

向下推墙:

沿着空格子走:

向右推墙:

向上推墙(\(2\) 步):

直接走到终点:(路线也标出来了)

然后按东南西北大写缩写的方式输出路线:

\(NESESEENNWNWWWWW\)

再不明白题目在讲什么我也无能为力了

题解

用 \(IDA^*\) 迭代加深搜索,关键是模拟推墙的过程需要细心观察题目的输入方法,发现把某一网格的权值转成二进制就变成了西北东南有没有墙的状态了。

所以用一些二进制运算操作就能模拟推墙过程了,比如删掉东边的一堵墙就是把权值减去 \(4\),判断东边有没有墙就用权值并(&)上 \(4\)。

注意推一堵墙会影响到很多格子。

至于估价函数,我们可以考虑算出当前点到每个出口的曼哈顿距离(横坐标之差加上纵坐标之差),再取最小值就好了。

完整代码加注释如下:

#include<bits/stdc++.h>

#define N 5
#define M 7
#define INF 0x7fffffff

using namespace std;

struct Point
{
	int x,y;
	Point(){};
	Point(int xx,int yy)
	{
		x=xx,y=yy;
	}
};

int stx,sty,a[N][M],ans[N*M];
int fx[]={0,-1,0,1},fy[]={-1,0,1,0},dir[]={1,2,4,8};
bool vis[N][M];

vector<Point>ed;//用来存所有出口的坐标

char change(int x)//把数字方向变成字符方向
{
	if(!x) return 'W';
	if(x==1) return 'N';
	if(x==2) return 'E';
	return 'S';
}

int check(int x,int y)//判断四周是否有出口
{
	if(y==1&&!(a[x][y]&1)) return 0;//西边是出口
	if(x==1&&!(a[x][y]&2)) return 1;//北边是出口
	if(y==6&&!(a[x][y]&4)) return 2;//东边是出口
	if(x==4&&!(a[x][y]&8)) return 3;//南边是出口
	return -1;//四周的格子没出口
}

int value(int x,int y)//估价函数
{
	int dis=INF;
	for(int i=0,size=ed.size();i<size;i++)
		dis=min(dis,abs(ed[i].x-x)+abs(ed[i].y-y));//曼哈顿距离
	return dis;
}

bool right(int x,int y)//判断是否在网格图内
{
	return x>=1&&x<=4&&y>=1&&y<=6;
}

bool IDAstar(int dep,int maxdep,int x,int y)//IDA*
{
	if(dep+value(x,y)+1>maxdep) return false;//剪枝
	int tmp=check(x,y);
	if(tmp!=-1)//有答案了
	{
		ans[dep+1]=tmp;
		return true;
	}
	for(int i=0;i<4;i++)
	{
		int xx=x+fx[i],yy=y+fy[i];
		if(!right(xx,yy)||vis[xx][yy])continue;//走过的不去
		if(!(a[x][y]&dir[i]))//(x,y)和(xx,yy)之间没有墙
		{
			vis[xx][yy]=true;
			ans[dep+1]=i;
			bool flag=IDAstar(dep+1,maxdep,xx,yy);
			vis[xx][yy]=false;
			if(flag) return true;//剪枝,一找到答案就回溯
		}
		else if(!(a[xx][yy]&dir[i]))//可以推墙
		{
        //下面以向东推墙举例,则墙原来在(x,y)东边、(xx,yy)西边
			a[x][y]-=dir[i];//因为把当前格东边的墙向东推了,所以东边的墙要减掉
			a[xx][yy]+=dir[i]-dir[(i+2)%4];//因为(xx,yy)西边的墙被推到了东边,所以要先减去西边,再加上东边
			int xi=xx+fx[i],yi=yy+fy[i];//(xx,yy)东边的格子(xi,yi)
			if(right(xi,yi))
				a[xi][yi]+=dir[(i+2)%4];//由于(xi,yi)西边原先没有墙,现在被推过来一堵墙,所以要加上西边的墙
			vis[xx][yy]=true;
			ans[dep+1]=i;
			bool flag=IDAstar(dep+1,maxdep,xx,yy);
			vis[xx][yy]=false;//还原
			if(right(xi,yi))
				a[xi][yi]-=dir[(i+2)%4];
			a[xx][yy]-=dir[i]-dir[(i+2)%4];
			a[x][y]+=dir[i];
			if(flag) return true;//剪枝
		}
	}
	return false;
}

int main()
{
	while(~scanf("%d%d",&sty,&stx)&&(stx||sty))
	{
		for(int i=1;i<=4;i++)
		{
			for(int j=1;j<=6;j++)
			{
				scanf("%d",&a[i][j]);
				if(j==1&&!(a[i][j]&1)) ed.push_back(Point(i,j));//看是否是出口
				else if(j==6&&!(a[i][j]&4)) ed.push_back(Point(i,j));
				else if(i==1&&!(a[i][j]&2)) ed.push_back(Point(i,j));
				else if(i==4&&!(a[i][j]&8)) ed.push_back(Point(i,j));
			}
		}
		vis[stx][sty]=true;
		for(int maxdep=1;;maxdep++)//不断加深最大步数
		{
			if(IDAstar(0,maxdep,stx,sty))
			{
				for(int i=1;i<=maxdep;i++)
					putchar(change(ans[i]));
				puts("");
				break;
			}
		}
		vis[stx][sty]=false;//不要忘了这步
	}
	return 0;
}

标签:yy,推墙,return,Wall,网格,UVA10384,int,xx,IDA
From: https://www.cnblogs.com/ez-lcw/p/16843063.html

相关文章

  • 【WPF】二、Validation 数据验证
    上一篇:【WPF】一、WPF数据验证机制Validation---重要只设计Mvvm的View层和Viewmodel层,未设计到model。下面一篇重点介绍IDataErrorInfo|INOtyfyDataErrorInfo+数据标注......
  • javax.validation 请求参数校验小问题: @Min 不校验是否为空
    想用@Min来校验是否为空, 结果发现不行, 看来是必须用到@NotNull 注解了.如下. 我的代码是:@Min(value=0,message=MsgCdConstant.AMOUNT_MUST_BE_POSITIVE)h......
  • Firewalld防火墙
    概述firewalld防火墙是centos7系统默认的防火墙管理工具,取代了之前的iptables防火墙,也是工作在网络层,属于包过滤防火墙。支持IPv4、IPv6防火墙设置以及以太网桥支持服......
  • oppo r9m mt6755 frida 手机自动重启
    最近在oppor9m手机上安装Frida,每次运行frida-server的时候,手机就会自动重启,经过查询,觉得应该是frida和CPU不匹配导致的oppor9m手机上使用的是联发科heliop10也就是mt67......
  • 使用Expression代替反射读取IDataReader或IDataRecord给实体类赋值
    ExpressionMapper代码usingSystem;usingSystem.Collections.Concurrent;usingSystem.Collections.Generic;usingSystem.Data;usingSystem.Data.Common;usingSystem.Li......
  • hibernate-validator 参数校验2(补充)
    目录一@Validated分组校验(单层对象)1.1分组校验测试参数1.2分组接口1.3controller测试接口二@Validated根据前端的传参状态进行校验(单层对象)2.1controller测试接口2.......
  • Linux 系统防火墙 Firewall-cmd 日常操作指南
    1. 管理端口列出dmz级别的被允许的进入端口#firewall-cmd--zone=dmz--list-ports允许tcp端口8080至dmz级别#firewall-cmd--zone=dmz--add-port=8080/tcp允许......
  • 【SCOI2005】骑士精神(IDA_,A_)
    我们先考虑最纯粹的暴力,也就是暴力枚举每次空格调到哪里,并继续递归求解。然后发现\(O(8^{15}\times5\times5)\)的复杂度限制了我们的想象。同学写了一发好像10分然后既......
  • MyModel fields ValidationError clean_fields
    classMyModel(models.Model):foo=models.BooleanField()#Wrong!Don'tdothis!defclean_fields(self,exclude=None):#指定某些字段排除验证#Bah!Forg......
  • 安卓逆向 IDA 静态调试分析
    1.找到我们分析的接口  2.F5进入C伪代码修正一下参数,IDA无法正常识别jstring__fastcallJava_com_example_sfs_MainActivity_getText(JNIEnv*a1){return(*......