How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

Can someone tell me what am I doing wrong?


Editorial: ( I followed the DP solution O((n*m)^2) )

My approach: rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board[x2][y2] = ‘0’.

If it is correct then find it’s perimeter and if it’s greater then answer then answer=perimeter ie ans=max(ans,dp[i][j][p][q])

so dp[ i ][ j ][ i ][ j ]=1 for all i,j when v[i][j]==0. Because from point p1 to point p1, ie the same point always have a perimeter is the base case.

signed main(){     int r,c;cin>>r>>c;     vector<vi> v(r,vi(c));//2d array v[r][c]     bool dp[25][25][25][25]={false};//i,j to p,q     for(int i=0;i<r;i++){         string s;cin>>s;         for(int j=0;j<c;j++){             v[i][j]=(s[j]-'0');             if(v[i][j]==0)dp[i][j][i][j]=true;         }     }     int ans=-1;     for(int i=0;i<r;i++){         for(int j=0;j<c;j++){             for(int p=i;p<r;p++){                 for(int q=j;q<c;q++){                     //i,j to p,q , 0,0 0,2, afrom 1 to p, b from 1 to q                     if(!(i==p && j==q)){                         if(p-1>=0 && q-1>=0)                             dp[i][j][p][q]=(dp[i][j][p-1][q] && dp[i][j][p][q-1] && (v[p][q]==0));                         if(dp[i][j][p][q]==true){                             ans=max(ans,2*(p-i+q-j+2));                         }                     }                 }             }         }     }     cout<<ans; } 

Island Perimeter

The task is taken from leetcode

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.



[[0,1,0,0],  [1,1,1,0],  [0,1,0,0],  [1,1,0,0]] 

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below: enter image description here

My solution

/**  * @param {number[][]} grid  * @return {number}  */ var islandPerimeter = function(grid) {   const getWaterNeighborAt = position => {     if (!grid[position.y][position.x]) { return 0; }      const north = position.y - 1 < 0 ? true : grid[position.y - 1][position.x] === 0;     const east = position.x + 1 >= grid[0].length ? true : grid[position.y][position.x + 1] === 0;     const south = position.y + 1 >= grid.length ? true : grid[position.y + 1][position.x] === 0;     const west = position.x - 1 < 0 ? true : grid[position.y][position.x - 1] === 0;      return north + east + south + west;   };   let perimeter = 0;   grid.forEach((row, y) => {     row.forEach((_, x) => {       perimeter += getWaterNeighborAt({x, y});     });   });   return perimeter; }; 

How to print the perimeter of a square using asterisks on Python?

I want to write a program that asks the user to enter the length of the side of a square then display a square composed of asterisks along its perimeter, such as shown below: enter image description here

enter image description here

My coding attempt is as follows:

answer = input("Enter the length of square: ") length = int(answer)  for i in range(1, length+1):   if(i == 1 or i == length):     for k in range(1, length+1):       print("*", end="")   else:     for k in range(1, length+1):       if(k == 1):         print("*", end="")       elif(k < length):         print(" ", end="")       else:         print("*") 

But the output is not quite what I want. For example, if I enter 5 as the length of the side, I get the following output:

enter image description here

And note that I’m still a beginner with Python so I don’t know anything beyond loops so far (in case there’s an alternative way without the use of a for loop). Does anyone know what’s wrong with my code?

Does Magic Circle prevent non-weapon melee attacks across the circle’s perimeter?

The Magic Circle spell creates a circle that protects against certain types of creatures, and states:

[A creature of one of those types] can’t willingly enter the Cylinder by nonmagical means. If the creature tries to use teleportation or interplanar travel to do so, it must first succeed on a Charisma saving throw.

[A creature of one of those types] has disadvantage on Attack rolls against Targets within the Cylinder.

Such a creature tries to make an unarmed melee attack against a creature fully within the cylinder. What happens?

  1. They cannot do so, because part of their body entering the cylinder is treated the same as their whole body entering the cylinder.
  2. They can do so, but have disadvantage. They are not trying to “enter” the cylinder, just briefly extending their body into it.

Question about determining area of a right triangle, perimeter given, hypotenuse value given in terms of one of the legs.

Hello I have a question about a difficult problem.
The problem states:
Right Triangle- perimeter of 84, and the hypotenuse is 2 greater than the other leg. Find the area of this triangle.
I have tried different methods of solving this problem using Pythagorean Theorem and systems of equations, but cannot find any of the side lengths or the area of the right triangle. I looked for similar problems on StackExchange and around the internet, but could not find anything.
Does anyone know anything that could help find the side lengths of the triangle and the area as well?


Anisotropic perimeter and regularity of anisotropic minimal surfaces

1. Introduction.

By-now classical results assert that minimal surfaces (in $ \mathbb R^n$ ) are generically “smooth” out of a “small” set.

Question. What are the known regularity results for anisotropic minimal surfaces?

2. A more detailed version of the question

For instance, reading a 1972 paper by Bombieri and Giusti I found the following definition:

Definition. A set $ A \subset \mathbb R^n$ has an oriented boundary of least area if $ \chi_A \in BV(\mathbb R^n)$ and for every $ g \in BV(\mathbb R^n)$ with compact support $ K$ we have $ $ \tag{1} P(A) := \vert D \chi_A\vert(K) \le \vert D(\chi_A + g)\vert(K) $ $ in the sense of measures, being $ \chi_A$ the characteristic function of the set $ A$ and $ P(A)$ the Euclidean perimeter of $ A$ .

The authors say – right after the definition – that “It is known that if $ A$ has oriented boundary of least area then [..] the boundary is an analytic hypersurface, except possibly for a closed set whose Hausdorff dimension does not exceed $ n-8$ “.

I would like to investigate the analogue of this problem in the anisotropic case. Let me clarify what I mean: let $ f \colon \mathbb R^n \to [0,+\infty)$ be some good function (say non-negative, convex and positively 1-homogeneous, as usual in Calculus of Variations). We define the anisotropic perimeter of a set $ A$ (of finite perimeter) by $ $ P_f(A) := \int_{\partial^e A} f(\nu_A(x))\, d\mathcal H^{n-1}(x) $ $ where $ \nu_A$ is the measure theoretic outer unit normal, $ \partial^e A$ is the essential boundary and $ \mathcal H^{n-1}$ is the Hausdorff measure.

What is the analogue of (1) in this case? And are there known regularity results for the solutions to this minimum problem? Can you point out some reference to the literature investigating this problem? Thanks.