程序地带

广搜


青藤oj #10116. 迷宫
题目描述

在N*N的迷宫内,“#”为墙,“.”为路,“s”为起点,“e”为终点,一共4个方向可以走。从左上角((0,0)“s”)位置处走到右下角((n-1,n-1)“e”)位置处,可以走通则输出YES,不可以走则输出NO。


输入格式

输入的第一行为一个整数m,表示迷宫的数量。


其后每个迷宫数据的第一行为一个整数n(n≤16),表示迷宫的边长,接下来的n行每行n个字符,字符之间没有空格分隔。


输出格式

输出有m行,每行对应的迷宫能走,则输出YES,否则输出NO。


思路

从1,1开始判断四周是否可以走; 如果可以,就从下一个位置继续判断下一个位置是否能走,直到下一个位置是’e‘时;


代码
#include<bits/stdc++.h>
using namespace std;
char a[20][20];
int m,n;
int d(int x,int y)
{
if(a[x][y+1]=='e'||a[x+1][y]=='e'||a[x][y]=='e')
return 1;
a[x][y]='#';
if(a[x][y+1]=='.')
{
if(d(x,y+1))
return 1;
}
if(a[x+1][y]=='.')
{
if(d(x+1,y))
return 1;
}
if(a[x-1][y]=='.')
{
if(d(x-1,y))
return 1;
}
if(a[x][y-1]=='.')
{
if(d(x,y-1))
return 1;
}
return 0;
}
int main()
{
cin>>m;
while(m>=1)
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cin>>a[i][j];
}
if(d(1,1)==1)
cout<<"YES";
else
cout<<"NO";
m--;
}
}
青藤oj #10279. 装载问题
题目描述

Yours和zero在研究A启发式算法.拿到一道经典的A问题,但是他们不会做,请你帮他们.问题描述


在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。


输入格式

输入初试状态,一行九个数字,空格用0表示


输出格式

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)


思路

如果0不在最顶上,可以往上换; 如果0不在最右边,可以往右换; 如果0不在最左边,可以往左换; 如果0不在最下面,可以往下换; 直到状态等于123804765,停止循环;


代码
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
queue<string> q;
int main()
{
string n;
cin>>n;
q.push(n);
mp[n]=0;
while(!q.empty())
{
string state=q.front();q.pop();
if(state=="123804765")
{
cout<<mp[state];
return 0;
}
int p=state.find('0');
if(p>=3)
{
string now=state;
now[p]=state[p-3];
now[p-3]='0';
if(mp.find(now)==mp.end())
{
mp[now]=mp[state]+1;
q.push(now);
}
}
if(p%3!=0)
{
string now=state;
now[p]=state[p-1];
now[p-1]='0';
if(mp.find(now)==mp.end())
{
mp[now]=mp[state]+1;
q.push(now);
}
}
if(p%3!=2)
{
string now=state;
now[p]=state[p+1];
now[p+1]='0';
if(mp.find(now)==mp.end())
{
mp[now]=mp[state]+1;
q.push(now);
}
}
if(p<=5)
{
string now=state;
now[p]=state[p+3];
now[p+3]='0';
if(mp.find(now)==mp.end())
{
mp[now]=mp[state]+1;
q.push(now);
}
}
}
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Thomaswcy/article/details/112689358

随机推荐

电商专题-电商项目开发规模

1.网站并发数经过压力测试可以支持3000左右的并发,可以满足目前的业务需求。由于我们的系统是分布式架构,支持水平扩展,如果将来并发量提高的话,...

IT熊猫学院 阅读(658)

直解Java装箱和拆箱

Java装箱和拆箱什么是装箱和拆箱首先要清楚Java为8种基本类型都提供了对应的包装类装箱和拆箱是Java5提供的特性,装箱简单来说就是直接将基本类型转换为包装类,拆箱简单来说就是直接将包装类转换为基...

AStrangeJoker 阅读(139)

interview

HTML5新增的特性HTML5新增的特性:videoaudiocanvassvgcodemaintimeoutputprogressmark(高亮的引用文字)menutemplatena...

CV攻城师 阅读(137)

定向广播和全局广播的区别 四种广播类型

IP广播地址有四种类型:有限广播:就是255.255.255.255也叫做本地广播地址就是全局广播,默认路由器不转发。有限广播的地址设为255.255.255...

一十六笔画生 阅读(103)

ccxt k线数据_寻找相似的历史k线

ccxt k线数据_寻找相似的历史k线

有网友提问应该用什么样的数据库/数据结构/算法来计算某支股票的相似K线?具体的问题描述是,假设给出某股某段行情K线(单位/日),从任何其他股票历...

齐泉 阅读(501)

直接量

直接量直接量定义:指在程序中通过源代码直接给出的值。能指定直接量的有三种类型:基本类型、字符串类型、null类型。细讲这些类型:3.1int类型的直接量:有二...

苏处之 阅读(209)

潘少的安全密码-数组

ACM实验室的帅哥学长潘宇涛非常帅,但生活很随意,特别是他设置的银行卡密码太简单,一点都不安全,他女朋友对此很不满意,潘少为了哄女...

ichizy 阅读(558)