题意:从起点出发,可向东南西北4个方向走,如果前面没有墙则可走;如果前面只有一堵墙,则可将墙向前推一格,其余情况不可推动,且不能推动游戏区域边界上的墙。问走出迷宫的最少步数,输出任意一个移动序列。

分析:

1、最少步数--IDA*。

2、注意,若此墙可推动,必须改变当前格子,和沿当前格子向前一步的格子的墙的标记。

3、若沿当前格子向前两步的格子存在,则这个格子的墙的标记也要改变。不存在的情况是:把墙推向了边界。

4、因为每个格子的值是是1(如果正方形以西有一个墙),2(北),4(东)和8(南)的总和,所以通过与1,2,4,8 & 分别来判断西,北,东,南四个方向是否有墙。

5、可以通过当前步数与当前格子和最近边界的垂直距离的和是否大于maxn来剪枝。

6、注意起点要标记成已走过。

#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, -1, 0, 1, -1, -1, 1, 1};//西北东南
const int dc[] = {-1, 0, 1, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-15;
const int MAXN = 50 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int pic[10][10];
int vis[10][10];
int ans[30];
int maxn;
const string s = "WNES";
int dir[] = {1, 2, 4, 8};
int solve(int x, int y){
if(x == 1 && !(pic[x][y] & 2)) return 1;//此刻位于迷宫最北面,且当前格子北面没有墙
if(x == 4 && !(pic[x][y] & 8)) return 3;//东
if(y == 1 && !(pic[x][y] & 1)) return 0;//北
if(y == 6 && !(pic[x][y] & 4)) return 2;//南
return -1;
}
bool judge(int x, int y){
return x >= 1 && x <= 4 && y >= 1 && y <= 6;
}
bool dfs(int x, int y, int cur){
if(cur >= maxn) return false;
int tmp = solve(x, y);
if(tmp != -1){
ans[cur] = tmp;
return true;
}
for(int i = 0; i < 4; ++i){
int tx = x + dr[i];
int ty = y + dc[i];
if(judge(tx, ty) && !vis[tx][ty]){
if(!(pic[x][y] & dir[i])){//向pic[tx][ty]方向走,无墙
vis[tx][ty] = 1;
ans[cur] = i;
if(dfs(tx, ty, cur + 1)) return true;
vis[tx][ty] = 0;
}
else if(!(pic[tx][ty] & dir[i])){//向pic[tx][ty]方向走,有墙但可推
vis[tx][ty] = 1;
pic[tx][ty] += dir[i];//墙推动导致格子对墙的标记改变
pic[x][y] -= dir[i];
if(judge(tx + dr[i], ty + dc[i])){
pic[tx + dr[i]][ty + dc[i]] += dir[(i + 2) % 4];//注意对于该格子加反方向的墙,但是该格子可能不存在,比如把墙推向了边界
}
ans[cur] = i;
if(dfs(tx, ty, cur + 1)) return true;
if(judge(tx + dr[i], ty + dc[i])){
pic[tx + dr[i]][ty + dc[i]] -= dir[(i + 2) % 4];
}
pic[x][y] += dir[i];
pic[tx][ty] -= dir[i];
vis[tx][ty] = 0;
}
}
}
return false;
}
int main(){
int sx, sy;
while(scanf("%d%d", &sx, &sy) == 2){
if(!sx && !sy) return 0;
memset(ans, 0, sizeof ans);
for(int i = 1; i <= 4; ++i){
for(int j = 1; j <= 6; ++j){
scanf("%d", &pic[i][j]);
}
}
for(maxn = 1; ; ++maxn){
memset(vis, 0, sizeof vis);
vis[sy][sx] = 1;
if(dfs(sy, sx, 0)){
for(int i = 0; i < maxn; ++i){
printf("%c", s[ans[i]]);
}
printf("\n");
break;
}
}
}
return 0;
}

  

最新文章

  1. [转]Asp.Net Core 简单的使用加密的Cookie保存用户状态
  2. Asynchronous javascript and xml
  3. Java多线程有哪几种实现方式? Java中的类如何保证线程安全? 请说明ThreadLocal的用法和适用场景
  4. 20145213《Java程序设计》第三周学习总结
  5. 学习php前需要了解的知识
  6. UI4_UITableViewSectionIndex
  7. BSD历史
  8. Webstorm 配置与使用 Less
  9. 点击表格的单元格时实现变颜色,通过for循环为每个单元格添加一个onclick事件
  10. 使用vs code实现git同步
  11. org.apache.jasper.JasperException: The absolute uri: http://java.sun.com/jsp/jstl/core cannot be res
  12. Binary Tree Xorder Traversal
  13. ASP.NET Core - 开篇
  14. 【转载】Centos系统快速部署LNMP环境
  15. mybatis 中 foreach collection的三种用法(转)
  16. shell常用符号的意义
  17. IOS团队开发之——CocoaPods 第三方库管理工具
  18. Ubuntu 16.04系统下安装Discuz出现“HTTP ERROR 500”目前无法处理此请求
  19. 可视化库-seaborn-回归分析绘图(第五天)
  20. [CodeForces]CodeForces 13D 几何 思维

热门文章

  1. redis api-list
  2. ch6 列表和导航条
  3. ch5 创建类似按钮的链接
  4. Vue.js事件处理
  5. 非阻塞IO与异步IO
  6. 在Anaconda3环境下安装并切换 Tensorflow 2.0 环境
  7. Window Server 2019 配置篇(8)- 利用MDT定制自动加入域的脚本
  8. 51nod 1099:任务执行顺序 贪心
  9. HihoCoder第三周与POJ2406:KMP算法总结
  10. Visual Studio中的“build”、“rebuild”、“clean”的区别