# IMAGE - Image Perimeters

news/2024/4/21 1:38:54/

# IMAGE - Image Perimeters

## 题面翻译

### 描述
给出一张由"x"和"."组成的矩阵。每个"x"可以向上下左右及两个斜对角进行连通,请问由某个点开始的"x",它所连通的图形的周长为多少。
### 输入
整个测试有多组数据,整个测试以四个零代表结束。
对于每个数据,第一行给出整个图形的大小(长度小于50),再给出开始点的坐标。接下来若干行用于描述这个图形。
### 输出
如题

## 题目描述

Technicians in a pathology lab analyze digitized images of slides. Objects on a slide are selected for analysis by a mouse click on the object. The perimeter of the boundary of an object is one useful measure. Your task is to determine this perimeter for selected objects.

 The digitized slides will be represented by a rectangular grid of periods, '.', indicating empty space, and the capital letter 'X', indicating part of an object. Simple examples are

 **XX Grid 1 .XXX Grid 2**   
**XX .XXX**   
 **.XXX**   
 **...X**   
 **..X.**   
 **X...**

 An X in a grid square indicates that the entire grid square, including its boundaries, lies in some object. The X in the center of the grid below is _adjacent_ to the X in any of the 8 positions around it. The grid squares for any two adjacent X's overlap on an edge or corner, so they are connected.

 XXX   
X**X**X  Central X and adjacent X's   
XXX

 An object consists of the grid squares of all X's that can be linked to one another through a sequence of adjacent X's. In Grid 1, the whole grid is filled by one object. In Grid 2 there are two objects. One object contains only the lower left grid square. The remaining X's belong to the other object.

 The technician will always click on an X, selecting the object containing that X. The coordinates of the click are recorded. Rows and columns are numbered starting from 1 in the upper left hand corner. The technician could select the object in Grid 1 by clicking on row 2 and column 2. The larger object in Grid 2 could be selected by clicking on row 2, column 3. The click could not be on row 4, column 3.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/SP904/52be350def3b5baae704ab9cf4f5f069c1e5dfc4.png) One useful statistic is the perimeter of the object. Assume each X corresponds to a square one unit on each side. Hence the object in Grid 1 has perimeter 8 (2 on each of four sides). The perimeter for the larger object in Grid 2 is illustrated in the figure at the left. The length is 18.

 Objects will not contain any totally enclosed holes, so the leftmost grid patterns shown below could _NOT_ appear. The variations on the right could appear:

**Impossible Possible**

**XXXX XXXX XXXX XXXX**   
**X..X XXXX X... X...**   
**XX.X XXXX XX.X XX.X**   
**XXXX XXXX XXXX XX.X**

**..... ..... ..... .....**   
**..X.. ..X.. ..X.. ..X..**   
**.X.X. .XXX. .X... .....**   
**..X.. ..X.. ..X.. ..X..**   
**..... ..... ..... .....**

 The input will contain one or more grids. Each grid is preceded by a line containing the number of rows and columns in the grid and the row and column of the mouse click. All numbers are in the range 1-20. The rows of the grid follow, starting on the next line, consisting of '.' and 'X' characters.

 The end of the input is indicated by a line containing four zeros. The numbers on any one line are separated by blanks. The grid rows contain no blanks.

 For each grid in the input, the output contains a single line with the perimeter of the specified object.

 ```

Input:
2 2 2 2
XX
XX
6 4 2 3
.XXX
.XXX
.XXX
...X
..X.
X...
5 6 1 3
.XXXX.
X....X
..XX.X
.X...X
..XXX.
7 7 2 6
XXXXXXX
XX...XX
X..X..X
X..X...
X..X..X
X.....X
XXXXXXX
7 7 4 4
XXXXXXX
XX...XX
X..X..X
X..X...
X..X..X
X.....X
XXXXXXX
0 0 0 0
```
 ```

Output:
8
18
40
48
8
```

## 输入格式

## 输出格式


代码:

#include<iostream>
#include<algorithm>
using namespace std;char s[30][30];//网格表示
int rows, cols;//行列数
int total;//选中目标的周长
int chick_x, chick_y;//鼠标单击的目标坐标//对角线增量
int diagonal[4][2] = {{1,1},{-1,1},{-1,-1},{1,-1}
};
//垂直方向增量
int x_y[4][2] = {{1,0},{0,1},{-1,0},{0,-1}
};//标记已经统计过的坐标
int flag[30][30];//深搜
void work(int x, int y) {int i;int newx, newy;//标记坐标(x,y)为已经搜索过flag[x][y] = 1;//搜索水平垂直方向for (i = 0; i < 4; i++) {newx = x + x_y[i][0];newy = y + x_y[i][1];if ((s[newx][newy] == 'X') && flag[newx][newy] == 0)work(newx, newy);else if (s[newx][newy] == '.')total++;}//搜索对角线方向for (i = 0; i < 4; i++) {newx = x + diagonal[i][0];newy = y + diagonal[i][1];if ((s[newx][newy] == 'X') && flag[newx][newy] == 0)work(newx, newy);}
}int main() {int i, j;char imge[40];//初始化标记为全0for (i = 0; i < 30; i++)for (j = 0; j < 30; j++)flag[i][j] = 0;//初始化网格表示为全0memset(s, '.', sizeof(s));//输入行列数cin >> rows >> cols;//输入鼠标单击坐标cin >> chick_x >> chick_y;//构造网格for (i = 1; i < rows; i++) {cin >> imge[i];for (j = 1; j < cols; j++)s[i][j] = imge[j - 1];}work(chick_x, chick_y);cout << total;return 0;
}

运行结果: 

 


#include<iostream>
#include<algorithm>
using namespace std;char s[30][30];//网格表示
int rows, cols;//行列数
int total;//选中目标的周长
int chick_x, chick_y;//鼠标单击的目标坐标//对角线增量
int diagonal[4][2] = {{1,1},{-1,1},{-1,-1},{1,-1}
};
//垂直方向增量
int x_y[4][2] = {{1,0},{0,1},{-1,0},{0,-1}
};//标记已经统计过的坐标
int flag[30][30];//深搜
void work(int x, int y) {int i;int newx, newy;//标记坐标(x,y)为已经搜索过flag[x][y] = 1;//搜索水平垂直方向for (i = 0; i < 4; i++) {newx = x + x_y[i][0];newy = y + x_y[i][1];if ((s[newx][newy] == 'X') && flag[newx][newy] == 0)work(newx, newy);else if (s[newx][newy] == '.')total++;}//搜索对角线方向for (i = 0; i < 4; i++) {newx = x + diagonal[i][0];newy = y + diagonal[i][1];if ((s[newx][newy] == 'X') && flag[newx][newy] == 0)work(newx, newy);}
}int main() {int i, j;char imge[40];//初始化标记为全0memset(flag, 0, sizeof(flag));//初始化网格表示为全为  ‘.’memset(s, '.', sizeof(s));//输入行列数//输入鼠标单击坐标cin >> rows >> cols>>chick_x >> chick_y;//构造网格for (i = 1; i < rows; i++) {cin >> imge[i];for (j = 1; j < cols; j++)s[i][j] = imge[j - 1];}work(chick_x, chick_y);cout << total;return 0;
}

#include <iostream>
#include <cstring>
using namespace std;char s[60][60];     // 储存整个图像
bool vis[60][60];   // 访问标记数组,标记每个点是否已经被访问过
int n, m;           // 图像大小
int sx, sy;         // 开始搜索的起点
int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    // 方向数组,模拟八个方向移动
int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };void dfs(int x, int y, int& ans) {   // 深搜函数,引用类型传递 ans 变量vis[x][y] = true;               // 标记已经访问过for (int i = 0; i < 8; i++) {   // 枚举八个方向int nx = x + dx[i];int ny = y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 判断是否到达图像边界if (s[nx][ny] != 'X') continue;      // 如果不是 X,则无需访问if (vis[nx][ny]) continue;           // 如果已经访问过,则无需继续访问ans++;                              // 更新计数器dfs(nx, ny, ans);                   // 继续搜索}
}int main() {while (cin >> n >> m >> sx >> sy) {if (n == 0 && m == 0 && sx == 0 && sy == 0) break;    // 输入结束标识memset(vis, false, sizeof(vis));       // 初始化访问标记数组memset(s, '.', sizeof(s));             // 初始化整个图像为 '.'for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> s[i][j];     // 读入整个图像}}int ans = 1;    // 计数器,初始为 1dfs(sx, sy, ans);   // 调用深搜函数cout << ans * 2 << endl;    // 周长为连通块大小乘以 2}return 0;
}

 


http://www.ppmy.cn/news/48956.html

相关文章

程序员最常见的谎言

小伙伴们大家好&#xff0c;我是阿秀。 上周看到知乎上有位网友总结了自己的10年程序员生涯中最常说的一些谎言&#xff0c;一共有15条&#xff0c;看完我直呼内行&#xff01;&#xff01; 全中&#xff01;每一枪都中了&#xff01;每一条我都说过。 我基本都说过他说过的那些…

LVS负载均衡群集——NAT模式实操

1.1 群集的的定义及意义 群集的定义 Cluster&#xff0c;集群&#xff08;也称群集&#xff09;由多台主机构成&#xff0c;但对外只表现为一一个整体&#xff0c;只提供一-个访问入口(域名或IP地址)&#xff0c; 相当于一台大型计算机。 群集的作用 对于企业服务的的性能提升…

深入剖析 Qt QMap:原理、应用与技巧

目录标题 引言&#xff1a;QMap 的重要性与基本概念QMap 简介&#xff1a;基本使用方法&#xff08;QMap Basics: Concepts and Usage&#xff09;QMap 迭代器&#xff1a;遍历与操作键值对&#xff08;QMap Iterators: Traversing and Manipulating Key-Value Pairs&#xff0…

什么是BASE最终一致性

什么是BASE最终一致性 BASE最终一致性是指&#xff0c;在分布式系统中&#xff0c;数据副本可能存在不一致性&#xff0c;但最终数据会达成一致状态。BASE是指Basic Available&#xff08;基本可用&#xff09;、Soft State&#xff08;软状态&#xff09;和Eventually Consis…

更新整理了一大波热门免费可用的API大全

AI 智能 AI 绘画&#xff1a;通过AI 生成绝美图片&#xff0c;包括图生文、文生图、人像照片转动漫、图片高清化等。 人脸检测&#xff1a;快速检测图片中的人脸并返回人脸位置&#xff0c;输出人脸关键点坐标&#xff0c;支持识别多张人脸。 静态活体检测&#xff1a;静态活…

转换CAJ到PDF: 教你如何转换这两种文件格式

在现代信息化社会中&#xff0c;我们常常需要处理各种文件格式&#xff0c;例如常见的文本文档、PDF、图片、视频等等。其中&#xff0c;学术界或者专业人士常常会接触到一种叫做CAJ格式的文件&#xff0c;而这个格式在阅读、编辑以及分享方面可能存在一些限制。为了解决这个问…

反垃圾邮件产品技术要求

声明 本文是学习信息安全技术 反垃圾邮件产品技术要求和测试评价方法. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 反垃圾邮件产品技术要求 引言 为指导反垃圾邮件产品的研制、生产、测试和评价工作的开展&#xff0c;本标准依据《信息技术 安全技…

婚恋交友app开发中需要注意的安全问题

前言 随着移动设备的普及&#xff0c;婚恋交友app已经成为了人们生活中重要的一部分。但是&#xff0c;这些应用的开发者需要确保应用的安全性&#xff0c;以保护用户的隐私和数据免受攻击。本文将介绍在婚恋交友app开发中需要注意的安全问题。 在当今数字化时代&#xff0c;…

浏览器实时查看日志系统-log.io

标题 前言操作步骤1. Install server via npm安装Nodejs2. Launch server3. Install file input via npm4. Configure file input前言 log.io 是一个实时日志监控工具,采用 node.js + socket.io 开发,使用浏览器访问,每秒可以处理超过5000条日志变动消息。有一点要指出来的…

互联网摸鱼日报(2023-04-20)

互联网摸鱼日报&#xff08;2023-04-20&#xff09; InfoQ 热门话题 从 DevOps 到平台工程 &#xff5c;InfoQ《极客有约》 Node.js 20正式发布 华为孟晚舟&#xff1a;成功的数字化转型都由战略驱动&#xff0c;而非技术驱动 更懂业务的用友 iuap 平台&#xff0c;助力企业…

在Java8中使用Akka

提示&#xff1a;在Java8中&#xff0c;使用Akka可以轻松构建分布式、高可用、高可伸缩性的应用程序。Akka是一个基于actor模型的框架&#xff0c;它提供了强大的并发和分布式处理能力。在本文中&#xff0c;我们将介绍如何在Java8中使用Akka&#xff0c;并提供一些简单的例子帮…

GIS基础概念与开发实践

GIS的应用价值 呈现、还原、规划空间信息数据挖掘、统计分析等等 Q&#xff1a;这么多软件可以做GIS&#xff0c;但是格式又不一样&#xff0c;怎么办&#xff1f;这普需要一个标准的出现。 GIS标准&#xff1a;OGC标准 不同GIS软件对空间数据定义和存储结构不同&#xff0…

智能文案改写工具-智能改写工具免费

智能写作机器人 智能写作机器人&#xff0c;这是一种让人类写作变得更加简单的创新技术。它的出现&#xff0c;为内容生产领域带来了巨大的进步&#xff0c;不仅提高了人们的写作效率&#xff0c;还让优质的内容更容易被产生和共享。现在&#xff0c;让我们来了解一下智能写作…

使用华为云免费资源训练Paddle UIE模型

一、创建虚拟环境 好习惯&#xff0c;首先创建单独的运行环境 conda create -n uie python3.10.9 conda activate uie 二、安装paddle框架及paddlenlp 2.1 参考官方文档安装paddle 开始使用_飞桨-源于产业实践的开源深度学习平台 首先查看自己服务器cuda版本&#xff0c;…

线性表总结

线性表 目录&#xff1a; 文章目录 线性表概念一、线性表的定义二、线性表的基本操作三、线性表的实现方式四、线性表的应用总结 概念 线性表是一种基本的数据结构&#xff0c;由一系列具有相同类型的数据元素构成&#xff0c;这些元素之间具有线性的顺序关系&#xff0c;每个…

【代码调试】《Frustratingly Simple Few-Shot Object Detection》

更多问题可参考&#xff1a; https://blog.csdn.net/qiankendeNMY/article/details/128450196 论文地址&#xff1a;https://arxiv.org/abs/2003.06957 论文代码&#xff1a;https://github.com/ucbdrive/few-shot-object-detection 我的配置&#xff1a; Python &#xff1a…

axf文件、hex文件、bin文件区别

axf文件、hex文件与bin文件都可以运行在stm32&#xff0c;都存储了源代码通过编译器生成的机器码。 axf文件&#xff1a;编译默认生成的文件&#xff0c;包含代码数据和调试信息&#xff0c;在MDK里进行debug调试用的文件。 hex文件&#xff1a;使用十六进制符号表示的代码记…

校招又临近了,怎么在面试中应对设计模式相关问题呢?

夏天开始了&#xff0c;那么夏天结束时的毕业季也不远了。毕业是个伤感、期待而又略带残酷的时节&#xff0c;就像蜜桃无论成熟与否都会在这个时间被采摘&#xff0c;如果毫无准备就踏入社会&#xff0c;就会……马上变成低级社畜。所以说还是要早点为了毕业找工作做点准备&…

ElasticSearch集群搭建

一、ElasticSearch 集群 1.1 搭建集群 Elasticsearch如果做集群的话Master节点至少三台服务器或者三个Master实例加入相同集群&#xff0c;三个Master节点最多只能故障一台Master节点&#xff0c;如果故障两个Master节点&#xff0c;Elasticsearch将无法组成集群.会报错&…

设计模式详解-软件设计(五十六)

原创 真题详解(UML图)-软件设计&#xff08;五十五)https://blog.csdn.net/ke1ying/article/details/130311994 创建型、结构型、行为型 抽象工厂&#xff08;Abstruct Factory&#xff09; 提供一个创建系列相关或相互依赖的接口&#xff0c;无须指定他们具体的类。 适用于&…