# IMAGE - Image Perimeters

深藏阁楼爱情的钟 2024-03-23 14:23 57阅读 0赞

\# 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];
    
    	//初始化标记为全0
    	for (i = 0; i < 30; i++)
    		for (j = 0; j < 30; j++)
    			flag[i][j] = 0;
    
    	//初始化网格表示为全0
    	memset(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;
    }

运行结果：

![bac441b9c67a4ac2abcb971be7dccdd7.png][]

--------------------

#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];
    
    	//初始化标记为全0
    	memset(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;    // 计数器，初始为 1
            dfs(sx, sy, ans);   // 调用深搜函数
            cout << ans * 2 << endl;    // 周长为连通块大小乘以 2
        }
        return 0;
    }

![02a00a28f93345499fc75987c8392217.png][]

[bac441b9c67a4ac2abcb971be7dccdd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/25923438fb034b068360a458e252afd4.png
[02a00a28f93345499fc75987c8392217.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/09eb6dca654f41cfb817b8a168a1126f.png