hiho一下第159周《Region Perimeter》题目分析

3
1

《区域周长》

本题要求以某个格子为起点,找出一块连通区域,并且求出周长。

又是一道常见的2D地图上的搜索问题,做过hiho一下第156周《岛屿》这道题目的同学一定很熟悉。

我们把《岛屿》这题中使用的dfs稍加修改就能作为本题找出连通区域的基础算法:

dfs(i, j):
    int dx[4] = {-1, 1, 0, 0}
    int dy[4] = {0, 0, -1, 1}
    visited[i][j] = true
    for d = [0 .. 4):
        int _x = i + dx[d]
        int _y = j + dy[d]
        if (_x, _y) is inside the boarder AND NOT visited[_x][_y] AND grid[_x][_y] == gird[i][j]:
            dfs(_x, _y)

在此基础上我们需要思考如何计算区域的周长。对于一个区域中的方格来说,它一共有上下左右四条长度为1边。其中某条边是边界的一部分当且仅当这条边另一侧的方格不是本区域的方格或者根本不存在(在地图之外)。

所以在我们dfs的过程中,在从方格(i, j)尝试扩展到方格(_x, _y)时,可以顺便判断夹在(i, j)和(_x, _y)的之间的边是不是边界。如果是,我们就累计在变量ans中:

dfs(i, j):
    int dx[4] = {-1, 1, 0, 0}
    int dy[4] = {0, 0, -1, 1}
    visited[i][j] = true
    for d = [0 .. 4):
        int _x = i + dx[d]
        int _y = j + dy[d]
        if (_x, _y) is NOT inside the boarder:
            ans++
        else if NOT visited[_x][_y]:
            if grid[_x][_y] == gird[i][j]:
                dfs(_x, _y)
            else:
                ans++

10 answer(s)

1

使用DFS深度优先搜索,答案是对的,可惜时间复杂度超过了。

#include<iostream>
#include<vector>
#include<math.h>
#include<stack>
using namespace std;
int main()
{
    int n,m,x,y;
    int d[4][2]={{0,-1},{0,1},{-1,0},{1,0}};//左右上下
    while(cin>>n>>m>>x>>y)
    {
        vector<vector<int>>mx(n,vector<int>(m,0));
        vector<vector<int>>vs(n,vector<int>(m,0));
        stack<pair<int,int>>stk;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                int t=0;
                cin>>t;
                mx[i][j]=t;
            }
        }
        int c=1;
        vs[x][y]=1;
        stk.push(make_pair(x,y));
        while(!stk.empty())
        {
            x=stk.top().first;
            y=stk.top().second;
            for(int i=0;i<4;i++)
            {
                int tx=x+d[i][0];
                int ty=y+d[i][1];
                if(tx>=0&&tx<n&&ty>=0&&ty<m)
                {
                    if(vs[tx][ty]==0&&mx[tx][ty]==mx[x][y])
                    {
                        stk.push(make_pair(tx,ty));
                        vs[tx][ty]=1;
                        c++;
                        x=tx;
                        y=ty;
                        i=-1;
                    }
                    if(i==3)
                        stk.pop();
                }
            }
        }
        cout<<2*c+2<<endl;
    }
    return 0;
}
0

使用DFS深度优先搜索,答案是对的,可惜时间复杂度超过了。

include

include

include

include

using namespace std; int main() { int n,m,x,y; int d[4][2]={{0,-1},{0,1},{-1,0},{1,0}};//上下左右 while(cin>>n>>m>>x>>y) { vector>mx(n,vector(m,0)); vector>vs(n,vector(m,0)); stack>stk; for(int i=0;i>t; mx[i][j]=t; } } int c=1; vs[x][y]=1; stk.push(make_pair(x,y)); while(!stk.empty()) { x=stk.top().first; y=stk.top().second; for(int i=0;i<4;i++) { int tx=x+d[i][0]; int ty=y+d[i][1]; if(tx>=0&&tx=0&&ty

1

提供一种算周长的思路:每一行,从左到右,用cnt记录当前是处于矩形内还是矩形外的,那么遍历的同时由矩形内到矩形外就sum++,同理矩形外到矩形内也sum++,注意最后要sum+=cnt;

for(int i=0;i

之前做过一道计算三维表面积的,cnt记录的就是当前维度上的高度了

0

求助错误在哪

#include <iostream>
#include <string>  
using namespace std;
int num, f[101][101], d[101][101],n,m,x,y;
int sumline(int a, int b) {
        int l = 4;
        d[a][b] = -1;
        if (f[a][b] == f[a - 1][b]) {
            l--;
            if (d[a - 1][b]>-1&&a>0)
                sumline(a - 1, b);
        }
        if (f[a][b] == f[a + 1][b]&&a+1<n) {
            l--;
            if (d[a + 1][b]>-1)
                sumline(a + 1, b);
        }
        if (f[a][b] == f[a][b - 1]&&b>0) {
            l--;
            if (d[a][b - 1]>-1)
                sumline(a, b - 1);
        }
        if (f[a][b] == f[a][b + 1]&&b+1<m) {
            l--;
            if (d[a][b + 1]>-1)
                sumline(a, b + 1);
        }
        num += l;
    return true;
}
int main()
{
    cin >> n >> m >> x >> y;
    for (int i = 0; i<n; i++)
        for (int j = 0; j < m; j++) 
            cin >> f[i][j];
    cout << sumline(x, y) << endl; 
    return 0;
}
  • 1. 把 &&a>0 放在外层if上; 2. return num 不是 return true; 你这个程序样例都不会过吧,要掌握DEBUG的方法。

  • 添加评论
  • reply
0

请教一下, 如下代码为什么只得了40分,有什么特殊情况没有考虑到吗?

#include <bits/stdc++.h>

using namespace std;

int m,n,x,y;
int a[105][105];

inline bool inrange(int x, int y){
    return 0<=x && x<n && 0<=y && y<m;
}

int main(){
    scanf("%d %d %d %d\n", &n, &m, &x, &y);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    queue<pair<int,int> > Q;
    set<pair<int,int> > visit;
    Q.push(make_pair(x-1, y-1));
    int ofx[4]={0,-1,0,1};
    int ofy[4]={-1,0,1,0};
    int res = 0;
    while(!Q.empty()){
        pair<int, int> pos;
        pos = Q.front();
        Q.pop();
        int x = pos.first;
        int y = pos.second;
        int cnt = 0;
        for(int i =0;i<4;i++){
            pair<int,int> np = make_pair(x+ofx[i],y+ofy[i]);
            if (inrange(np.first,np.second) && a[x][y]==a[np.first][np.second]){
                cnt++;
                if (visit.find(np)==visit.end())
                    Q.push(np);
            }
        }
        res += 4-cnt;
        visit.insert(pos);
    }
    printf("%d\n", res);
    return 0;
}
  • 刚刚发现初始位置填错了,应该为<x,y>,但修改后也只有80分。

  • Q.push(np)的时候就应该同时visit.insert(np)了。不然可能处理多次同一个格子吧。

  • 添加评论
  • reply
1

提供一个计算周长的思路,每个方格4条边,每两个相邻的方格需要剪掉2条边

这样直接遍历dfs后的矩阵,对于一个是区域内的方格,看他的上下左右有没有区域内的方格,每有一个 -1 就行了(相邻的两个方格都会遍历到一次,每有一组相邻边数 -2)

0

sad

0

import java.util.Scanner; public class Main{

private static int x_min = Integer.MAX_VALUE, x_max = Integer.MIN_VALUE, y_min = Integer.MAX_VALUE, y_max = Integer.MIN_VALUE;

public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int x = sc.nextInt(); int y = sc.nextInt();

if(x < 0 || x >= N || y < 0 || y >= M){
    System.out.print(0);
    return;
}

int[][] num = new int[N][M];
for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
        num[i][j] = sc.nextInt();
    }
}

int[][] visited = new int[N][M];

visited(x, y, num, visited);

System.out.print((x_max - x_min + 1 + y_max - y_min + 1)*2);

}

private static void visited(int x, int y, int[][] num, int[][] visited) { visited[x][y] = 1; if(x < x_min) x_min = x; if(x > x_max) x_max = x; if(y < y_min) y_min = y; if(y > y_max) y_max = y;

if(x-1 > -1 && visited[x-1][y] != 1 && num[x-1][y] == num[x][y])
    visited(x-1, y, num, visited);
if(y-1 > -1 && visited[x][y-1] != 1 && num[x][y-1] == num[x][y])
    visited(x, y-1, num, visited);
if(x+1 < num.length && visited[x+1][y] != 1 && num[x+1][y] == num[x][y])
    visited(x+1, y, num, visited);
if(y+1 < num[0].length && visited[x][y+1] != 1 && num[x][y+1] == num[x][y])
    visited(x, y+1, num, visited);

} }

0

按照这种算法的话,如果出现空心的形状的,比如说“口”字形的岛屿,那么周长计算的是内周长加上外周长的,题目并没有说清楚,最开始我只算了外周长,结果过了90%。

1

为啥是70分额

import java.util.Scanner;

public class Main{

private static int x_min = Integer.MAX_VALUE, x_max = Integer.MIN_VALUE, y_min = Integer.MAX_VALUE, y_max = Integer.MIN_VALUE;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int x = sc.nextInt();
    int y = sc.nextInt();

    if(x < 0 || x >= N || y < 0 || y >= M){
        System.out.print(0);
        return;
    }

    int[][] num = new int[N][M];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            num[i][j] = sc.nextInt();
        }
    }

    int[][] visited = new int[N][M];

    visited(x, y, num, visited);

    System.out.print((x_max - x_min + 1 + y_max - y_min + 1)*2);
}

private static void visited(int x, int y, int[][] num, int[][] visited) {
    visited[x][y] = 1;
    if(x < x_min)
        x_min = x;
    if(x > x_max)
        x_max = x;
    if(y < y_min)
        y_min = y;
    if(y > y_max)
        y_max = y;

    if(x-1 > -1 && visited[x-1][y] != 1 && num[x-1][y] == num[x][y])
        visited(x-1, y, num, visited);
    if(y-1 > -1 && visited[x][y-1] != 1 && num[x][y-1] == num[x][y])
        visited(x, y-1, num, visited);
    if(x+1 < num.length && visited[x+1][y] != 1 && num[x+1][y] == num[x][y])
        visited(x+1, y, num, visited);
    if(y+1 < num[0].length && visited[x][y+1] != 1 && num[x][y+1] == num[x][y])
        visited(x, y+1, num, visited);
}

}

write answer 切换为英文 切换为中文


转发分享