# IMAGE - Image Perimeters

news/2024/11/2 17:26:56/

# 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;…