题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=646
题目类型: 搜索
题目:
By filling a rectangle with slashes (/) and backslashes (), you can generate nice
little mazes. Here is an example:
As you can see, paths in the maze cannot branch, so the whole maze only contains cyclic paths and paths entering somewhere and leaving somewhere else. We are only interested in the cycles. In our example, there
are two of them.
Your task is to write a program that counts the cycles and finds the length of the longest one. The length is defined as the number of small squares the cycle consists of (the ones bordered by gray lines in the
picture). In this example, the long cycle has length 16 and the short one length 4.
题目大意翻译:
用斜线和反斜杠来填写一个矩形,您可以生成漂亮的小迷宫。这里有一个例子:
如上图,可以组成一个迷宫,斜线和反斜杠相当于是迷宫的墙,路径在迷宫中不能分支, 所以整个迷宫只包含循环路径封闭(无法走出迷宫),
还有的路径是通向迷宫外面的。
你的任务是写一个程序, 计算出所形成的迷宫有多少个封闭路径(循环路径),以及计算出其中最长的封闭路径有多长。\
样例输入:
6 4
\//\\/
\///\/
//\\/\
\/\///
3 3
///
\//
\\\
0 0
样例输出:
Maze #1:
2 Cycles; the longest has length 16.
Maze #2:
There are no cycles.
分析与总结:
初看这题时,有点无所适从,主要是所给的图像并不是按常规、方格是斜着放的,这样的话,比较难转换成用数组来存。
后来,我发现题目所给的斜杆的长度是一个格子长的两倍,于是,便很自然的想到把原来的图像扩大两倍,在数组中用两个格子来存储一根斜线。
这样的话,就可以用数组来表示这个图像。
转换后的图如下(画得有点搓)
其中,五角星代表的格子数组中是空的(可以用一个符号来表示),这些格子是可以走的。
转换后,就可以很简单的用搜索做出这道题了。
其中需要注意的地方: 搜索时,可以往8个方向走,其中,往上、下、左、右走时,如果那个格子为空的,那么就可以直接走过去。
但是如果往斜着方向走时,仅仅是空的还不足以判断可以走,还需要再特判。
例如, 会出现如下情况:
这里从左上往右下走(或者从右下往左上走)时,虽然右下是空的,但是不可以走, 因为有斜杆”墙”阻挡着。
除了这种方法,还可以模拟光线反射的路径来做这题(我队友想到的就是这种方法),但是代码写起来的话会更难。
还有一种方法就是1格转换成9格,这种方法只要转换好之后, 搜索写起来是最容易的,因为不需要特判情况。
下面是1格转4格的代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int w,h, last_x, last_y;
char str[100][100], map[300][300];
int dir[8][2]={{1,0}, {-1,0}, {0,1},{0,-1}, // 这一行是上下左右方向走
{-1,1},{1,1},{1,-1},{-1,-1}}; // 这一行是斜的方向走,从左上开始,顺时针
bool vis[300][300];
// 把输入进行转换
void change(int row){
for(int i=0; i<strlen(str[row]); ++i){
int m_row=row*2, m_col=i*2;
if(str[row][i] == '\\' ){
map[m_row][m_col] = '\\';
map[m_row+1][m_col+1] = '\\';
map[m_row][m_col+1] = ' ';
map[m_row+1][m_col] = ' ';
}
else if(str[row][i] == '/'){
map[m_row][m_col+1] = '/';
map[m_row+1][m_col] = '/';
map[m_row][m_col] = ' ';
map[m_row+1][m_col+1] = ' ';
}
}
}
// 如果是斜着走,还要进行特判能否走
bool isPass(int x, int y, int dirNo){
int x1,y1,x2,y2; // x1为同row, x2为同col
x1 = x, y1=y+dir[dirNo][1];
x2 = x+dir[dirNo][0], y2=y;
if(dirNo==4 || dirNo==6){
if(map[x1][y1]=='/' && map[x2][y2]=='/')
return true;
}
else{
if(map[x1][y1]=='\\' && map[x2][y2]=='\\')
return true;
}
return false;
}
void dfs(int x,int y,int &cnt){
for(int i=0; i<8; ++i){
int dx=x+dir[i][0], dy=y+dir[i][1];
if(i<4) { // 如果是往上,下,左,右走
if(dx>=0 && dx<2*h && dy>=0 && dy<2*w && map[dx][dy]!='\\'&&map[dx][dy]==' ' && map[dx][dy]!='/' && !vis[dx][dy]){
vis[dx][dy] = true;
last_x = dx, last_y = dy; // 记住最后一个入栈的位置
++cnt;
dfs(dx,dy,cnt);
}
}
else{ // 如果是往斜的方向走
if(dx<0 || dx>=2*h || dy<0 || dy>=2*w || map[dx][dy]=='\\' || map[dx][dy]=='/' || vis[dx][dy])
continue;
if(isPass(x,y,i)){
vis[dx][dy] = true;
++cnt;
last_x = dx, last_y = dy;
dfs(dx, dy, cnt);
}
}
}
}
int main(){
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int cas=1;
while(~scanf("%d %d%*c",&w, &h) && w && h){
memset(str, 0, sizeof(str));
memset(map, 0, sizeof(map));
memset(vis, 0, sizeof(vis));
for(int i=0; i<h; ++i){
gets(str[i]);
change(i);
}
int maxNum=-2147483646, cnt, circleNum=0;
bool haveCircle = false;
for(int i=0; i<2*h; ++i){
for(int j=0; j<2*w; ++j){
if(map[i][j]==' ' && !vis[i][j]){
map[i][j] = '#';
cnt=1;
vis[i][j] = true;
dfs(i,j,cnt);
// 判断是否是环的,首先要判断结束的那点是否和开始的相邻
bool flag = false;
for(int k=0; k<8; ++k){
int dx=last_x+dir[k][0];
int dy=last_y+dir[k][1];
if(dx==i && dy==j){
flag=true; break;
}
}
// 相邻的还不够,数量至少是4才能形成环状
if(flag && cnt>=4){
haveCircle = true;
++circleNum;
if(cnt > maxNum)
maxNum = cnt;
}
}
}
}
printf("Maze #%d:\n",cas++);
if(haveCircle){
printf("%d Cycles; the longest has length %d.\n\n", circleNum, maxNum);
}
else{
printf("There are no cycles.\n\n");
}
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
uva705 Slash Maze 的代码,在UVaOJ上通过
21-triple-slash-directives(三斜线指令21).pdf
Laravel开发-phpnet-laravel-trailing-slash 在Laravel中添加带有尾随斜杠的重定向。
一个creator 小游戏,可以让小白了解creator 开发的基本流程,帮助他们入门
前端开源库-remove-trailing-slash删除尾随斜杠,删除尾随斜杠
资源来自pypi官网。 资源全名:discord-ext-slash-0.3.0rc1.tar.gz
discord-slash-commands,一个易于使用的软件包 如何安装 这很简单! 只需运行`npm i @ daimond113 / discord-slash-commands`,您就完成了! 如何使用 首先,如果您遇到了麻烦,可以在上询问,或者查看您将需要一...
dot-slash-2是的库版本,它是leiningen插件。 它使您可以创建具有其他名称空间代理的名称空间。 它以创建名为的命名空间的想法命名. 使用dev实用程序,可以从任何地方使用./foo语法访问它们,而无需任何操作。 ...
hack-n-slash-sprint 最初在大约12小时内创建的hack n'slash游戏。
斜线命令行脚本,可从Reddit用户提交的内容中下载唯一的文件安装$ git clone https://github.com/2yr434hgd7fy384/u-slash$ pip install u-slash/用法u-slash [OPTIONS] [USERNAMES]... DIRECTORYu-slash下载任意...
自用案例
discord-py-slash-command是第一个为Discord Bot API库制作的公共斜杠命令处理程序库。 安装 您可以使用下面的给定PIP行轻松安装discord-py-slash-command库: pip install -U discord-py-slash-command 免责声明...
npm i discord-slash-commands 特征 可客制化 多命令支持 每个行会命令支持 例子 const Discord = require ( 'discord.js' ) ; const client = new Discord . Client ( ) ; const { Slash } = require ( 'discord-...
连接-url-斜杠-消毒剂从你的快递网址中删除不必要的斜线的中间件安装 npm install connect-url-slash-sanitiser --save用法 var express = require('express');var urlSlashSanitiser = require('connect-url-slash-...
hapi-trailing-slash# 一个插件,用于处理传入URL的常见尾随斜杠问题,以便my-route和my-route /具有一致的行为。安装npm install hapi-trailing-slash基本用途此插件将注册一个preResponse扩展名,该扩展名将在...
欢迎来到Discord Slash Bot :waving_hand: 该机器人是一个简单的Discord Slash Bot。 :house: 用法 克隆回购 使用命令npm install或yarn安装依赖项 将.env.example重命名为.env并填写所需的空白 通过此邀请将漫游...
运行工作示例克隆示例,并使用以下版本在最新的Tomcat 8上运行: $ mvn clean package cargo:run 打开 笔记没有尾随/ 按登录按钮显示“ Hello”页面映射到/* 切换到slash-star分支,该分支将DispatcherServlet映射到...
vim-slash加强缓冲的搜索体验
npm install koa-no-trailing-slash 用法 const app = new ( require ( 'koa' ) ) ; app . use ( require ( 'koa-no-trailing-slash' ) ( ) ) ; app . use ( async ( ctx , next ) => { ctx . response . body = '...
$ npm i --save djs-slash-commands 用法 必需的: 导入和初始化处理程序: const { SlashCommandHandler } = require ( "djs-slash-commands" ) ; client . SlashCommands = new SlashCommandHandler ( client )...