嵊州D1T2 圣女
嵊州D1T2
圣女
马格里多希望为自己死去却身体不腐的女儿申请圣女。
只是,他不知道神圣的基督教和教皇已经腐朽到了何种地步!
22 年来,他辗转教皇国的各个教堂,但各个教堂都只会以各种理由搪塞、推辞。
教皇国可以看做一个 n ∗ n 的矩形,每个位置都有一个教堂,教堂有不同的种类。教皇所在的位置是 (n, n),马格里多可以在 (1, 1) (1.n) (n, 1) 中任意一个位置开始自己的旅程。
A 教堂:马格里多可以在牧师的指引下向上/下/左/右任意一个方向移动一格。
B 教堂:马格里多可以在牧师的指引下向上/下/左/右任意一个方向移动两格。
C 教堂:马格里多可以在牧师的指引下向左上/左下/右上/右下任意一个方向移动一格。
D 教堂:贪婪的牧师或者教皇会卷走马格里多的所有财产,使他不能继续自己的旅程。
马格里多经历每个教堂都需要一天的时间。
如果他不能为自己的女儿申请为圣女,请告诉他“Go to find Marx”,否则请告诉他,他的旅程最少需要多少天?
Input
第一行一个整数 n; 接下来 n 行,每行 n 个字母(A, B, C, D)表示教堂的种类。
Output
第一行一个整数表示最少的天数或者“Go to find Marx”(“引号不要输出”)
Examples
saint.in saint.out
3 ADC DAC ACA Go to find Marx
3 AAA CAA AAA 3
Notes
对于所有数据,满足 n ≤ 1000。
Task1[40pts]
n ≤ 4
Task2[10pts]
只有 A,B 且 B 的个数小于等于 5
Task3[10pts]
没有 D
Task4[40pts]
无特殊限制
solve!
这是一道典型的走迷宫的例题,用搜索嘛。
至于是DFS(深搜)还是BFS(广搜),我们有很大很大的争论。
下午讲题时,老师的题解上
所以我要认真研究一下两种搜索,都要!
基本思路
A:上下左右全部搜B:上下左右两格全部搜C:四个斜角全部搜D:直接return;
//3 AAA CAA AAA
//测试数据
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
char dt[][];
bool bj[][],ans=;
const int inf = 0x3f3f3f;
int n,d=,day=,minday=inf;
void jt(int x,int y){//dt[x][y]就是当前那个人在的地方
if(!(x>=&&x<=n&&y>=&&x<=n)) return;//确保数组不越位
if(bj[x][y]) return;
bj[x][y]=true;//标记 bool flag=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
flag=bj[i][j]&&flag;
if(flag){
ans=;
minday=min(minday,day);
}
//搜索
if(dt[x][y]=='A')
{
day++;
jt(x+,y);
jt(x-,y);
jt(x,y+);
jt(x,y-);
day--;
}
if(dt[x][y]=='B')
{
day++;
jt(x+,y);
jt(x-,y);
jt(x,y+);
jt(x,y-);
day--;
}
if(dt[x][y]=='C')
{
day++;
jt(x+,y+);
jt(x-,y+);
jt(x+,y-);
jt(x-,y-);
day--;
}
if(dt[x][y]=='D') return; bj[x][y]=false;
return;
}
int main()
{
//freopen("saint.in","r",stdin);
//freopen("saint.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
dt[i][j]=getchar();
}
jt(,n);
jt(,);
jt(n,);
if(ans)
printf("%d",minday);
else
printf("Go to find Marx");
return ;
}
没问题!
开始的问题嘛,在于忘记先判断dt(地图)[x][y]是否已经被标记过了
OK!
最新文章
- JavaScript对象和数组
- C语言学习 第十一次作业总结
- 轻量级前端MVVM框架avalon - 执行流程2
- BZOJ 1564: [NOI2009]二叉查找树
- 译文---C#堆VS栈(Part Two)
- hdu 4850 Wow! Such String!(字符串处理,yy)
- ORA-00257错误
- android120 zhihuibeijing 开机页面
- debian 颜色设置
- [转]mysql导入导出数据中文乱码解决方法小结
- java文件读写操作类
- 每天一个Linux命令 8
- php中(包括织梦cms)set_time_limit(0)不起作用的解决方法
- TabTopAutoTextSizeLayout【自定义文字字号区域(动态选项卡数据且可滑动)】
- [20180627]测试bbed是否支持管道命令.txt
- 在notepad++中运行python代码
- cocos2dx 3.x 开发环境搭建
- D. Relatively Prime Graph
- 6.5(java学习笔记)其他流(字节数组流,数据流,对象流,打印流)
- Boostrap常用组件英文名
热门文章
- WPF Binding的代码实现
- 日志文件 清理or压缩
- Bootstrap 分页翻页
- 为什么腾讯总能做出好产品?(在互联网行业,往往仅凭一个关键产品就足以改变整个公司的格局)MSN失败在不以用户体验为中心
- Win10《芒果TV》商店版更新v3.1.4.0:适配Xbox手柄B键后退、手机支持暗色主题不伤眼
- CPU和GPU双低效,摩尔定律之后一万倍 ——写于TPU版AlphaGo重出江湖之际
- UWP项目生成错误: 未能使用“CompileXaml”任务的输入参数初始化该任务。“CompileXaml”任务不支持“PlatformXmlDir”参数。请确认该参数存在于此任务中,并且是可设置的公共实例属性。
- Android零基础入门第37节:初识ListView
- springboot 2.x处理404、500等异常
- MSYS2 瘦身小攻略(使用junction)