原文:
给定维度为 m * n 的二进制 arr【】表示网格，其中“ 0 ”表示在单元的主对角线上有一堵墙，而“ 1 ”表示在单元的交叉对角线上有一堵墙。任务是针对每一个 i 第 行打印一个可以逃离网格的行的索引，假设一个人不能逃离网格的顶部或底部。
示例:
输入: arr[][] = {{1，1，0，1}，{1，1，0，0}，{1，0，0，0}，{1，1，0，1}，{0，1，0，1}} 输出: -1 -1 2 3 -1 解释:
第 0、1 或 4 行不存在转义路径。 如果一个人从第 2 行第行进入网格，那么他将按照上图所示的路径从单元(2，3)中出来。 如果一个人从 3 第行进入网格，那么他将按照上图所示的路径从单元(3，3)中出来。
输入: arr[][] = {{1，1，0}，{0，1，0}，{0，1，0}，{0，1，0}} 输出: -1 2 3 -1
方法:给定的问题可以基于以下观察来解决:
- 从上面的图像可以观察到，对于给定的壁取向，取决于人进入细胞的方向，只有一种选择用于离开该细胞。
- 因此，对于每一行，想法是在给定的方向上迭代，跟踪一个人进入单元格的方向。
按照以下步骤解决问题:
- ，并执行以下操作:
- 初始化两个变量，比如 i 和 j 来存储该人当前所在单元格的行索引和列索引。
- 将行分配给 i ，将 0 分配给 j 。
- 初始化一个变量，比如 dir，来存储一个人进入单元格的方向。
- 重复直到 j 至少不是 n 并执行以下操作:
- 如果 arr[i][j] 为 1 ，则检查以下情况:
- 如果 dir 等于“ l ，那么将 i 减 1 ，并将 d 赋给 dir 。
- 否则，如果 dir 等于“ u ，则将 j 减 1 ，并将“ r 赋给 dir 。
- 否则，如果 dir 等于“ r ，那么将 i 增加 1 ，并将 u 分配给 dir 。
- 否则，将 j 增加 1 ，并将 l 分配给 dir 。
- 否则，如果 arr[i][j] 为 0 ，则检查以下情况:
- 如果 dir 等于“ l ，那么将 i 增加 1 ，并将 u 分配给 dir 。
- 否则，如果 dir 等于“ u ，那么将 j 增加 1 ，并将 l 分配给 dir 。
- 否则，如果 dir 等于“ r ，那么将 i 减 1 ，并将 d 赋给 dir 。
- 否则，将 j 减 1 ，并将 r 分配给 dir 。
- 否则，如果 i 或 j 为 0 或 i 等于 m 或 j 等于 n 则断开。
- 如果 arr[i][j] 为 1 ，则检查以下情况:
- 如果 j 等于 n ，则打印值 i 。
- 否则，打印 -1 。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
// function to find the row index for
// every row of a matrix from which one
// can exit the grid after entering from left
void findpath(vector >& arr,
int m, int n)
{
// iterate over the range [0, m-1]
for (int row = 0; row < m; row ) {
// stores the direction from
// which a person enters a cell
char dir = 'l';
// row index from which
// one enters the grid
int i = row;
// column index from which
// one enters the grid
int j = 0;
// iterate until j is atleast n-1
while (j < n) {
// if mat[i][j] is equal to 1
if (arr[i][j] == 1) {
// if entry is from left cell
if (dir == 'l') {
// decrement i by 1
i--;
// assign 'd' to dir
dir = 'd';
}
// if entry is from upper cell
else if (dir == 'u') {
// decrement j by 1
j--;
// assign 'r' to dir
dir = 'r';
}
// if entry is from right cell
else if (dir == 'r') {
// increment i by 1
i ;
// assign 'u' to dir
dir = 'u';
}
// if entry is from bottom cell
else if (dir == 'd') {
// increment j by 1
j ;
// assign 'l' to dir
dir = 'l';
}
}
// otherwise,
else {
// if entry is from left cell
if (dir == 'l') {
// increment i by 1
i ;
// assign 'u' to dir
dir = 'u';
}
// if entry is from upper cell
else if (dir == 'u') {
// increment j by 1
j ;
// assign 'l' to dir
dir = 'l';
}
// if entry is from right cell
else if (dir == 'r') {
// decrement i by 1
i--;
// assign 'd' to dir
dir = 'd';
}
// if entry is from lower cell
else if (dir == 'd') {
// decrement j by 1
j--;
// assign 'r' to dir
dir = 'r';
}
}
// if i or j is less than 0 or i is
// equal to m or j is equal to n
if (i < 0 || i == m || j < 0 || j == n)
break;
}
// if j is equal to n
if (j == n)
cout << i << " ";
// otherwise
else
cout << -1 << " ";
}
}
// driver code
int main()
{
// input
vector > arr = { { 1, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
int m = arr.size();
int n = arr[0].size();
// function call
findpath(arr, m, n);
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for the above approach
import java.util.*;
class gfg{
// function to find the row index for
// every row of a matrix from which one
// can exit the grid after entering from left
static void findpath(int [][]arr,
int m, int n)
{
// iterate over the range [0, m-1]
for(int row = 0; row < m; row )
{
// stores the direction from
// which a person enters a cell
char dir = 'l';
// row index from which
// one enters the grid
int i = row;
// column index from which
// one enters the grid
int j = 0;
// iterate until j is atleast n-1
while (j < n)
{
// if mat[i][j] is equal to 1
if (arr[i][j] == 1)
{
// if entry is from left cell
if (dir == 'l')
{
// decrement i by 1
i--;
// assign 'd' to dir
dir = 'd';
}
// if entry is from upper cell
else if (dir == 'u')
{
// decrement j by 1
j--;
// assign 'r' to dir
dir = 'r';
}
// if entry is from right cell
else if (dir == 'r')
{
// increment i by 1
i ;
// assign 'u' to dir
dir = 'u';
}
// if entry is from bottom cell
else if (dir == 'd')
{
// increment j by 1
j ;
// assign 'l' to dir
dir = 'l';
}
}
// otherwise,
else
{
// if entry is from left cell
if (dir == 'l')
{
// increment i by 1
i ;
// assign 'u' to dir
dir = 'u';
}
// if entry is from upper cell
else if (dir == 'u')
{
// increment j by 1
j ;
// assign 'l' to dir
dir = 'l';
}
// if entry is from right cell
else if (dir == 'r')
{
// decrement i by 1
i--;
// assign 'd' to dir
dir = 'd';
}
// if entry is from lower cell
else if (dir == 'd')
{
// decrement j by 1
j--;
// assign 'r' to dir
dir = 'r';
}
}
// if i or j is less than 0 or i is
// equal to m or j is equal to n
if (i < 0 || i == m || j < 0 || j == n)
break;
}
// if j is equal to n
if (j == n)
system.out.print(i " ");
// otherwise
else
system.out.print(-1 " ");
}
}
// driver code
public static void main(string[] args)
{
// input
int [][]arr = { { 1, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
int m = arr.length;
int n = arr[0].length;
// function call
findpath(arr, m, n);
}
}
// this code is contributed by shikhasingrajput
python 3
# python3 program
# for the above approach
# function to find the row index for
# every row of a matrix from which one
# can exit the grid after entering from left
def findpath(arr, m, n) :
# iterate over the range [0, m-1]
for row in range(m):
# stores the direction from
# which a person enters a cell
dir = 'l'
# row index from which
# one enters the grid
i = row
# column index from which
# one enters the grid
j = 0
# iterate until j is atleast n-1
while (j < n) :
# if mat[i][j] is equal to 1
if (arr[i][j] == 1) :
# if entry is from left cell
if (dir == 'l') :
# decrement i by 1
i -= 1
# assign 'd' to dir
dir = 'd'
# if entry is from upper cell
elif (dir == 'u') :
# decrement j by 1
j -= 1
# assign 'r' to dir
dir = 'r'
# if entry is from right cell
elif (dir == 'r') :
# increment i by 1
i = 1
# assign 'u' to dir
dir = 'u'
# if entry is from bottom cell
elif (dir == 'd') :
# increment j by 1
j = 1
# assign 'l' to dir
dir = 'l'
# otherwise,
else :
# if entry is from left cell
if (dir == 'l') :
# increment i by 1
i = 1
# assign 'u' to dir
dir = 'u'
# if entry is from upper cell
elif (dir == 'u') :
# increment j by 1
j = 1
# assign 'l' to dir
dir = 'l'
# if entry is from right cell
elif (dir == 'r') :
# decrement i by 1
i -= 1
# assign 'd' to dir
dir = 'd'
# if entry is from lower cell
elif (dir == 'd') :
# decrement j by 1
j -= 1
# assign 'r' to dir
dir = 'r'
# if i or j is less than 0 or i is
# equal to m or j is equal to n
if (i < 0 or i == m or j < 0 or j == n):
break
# if j is equal to n
if (j == n) :
print(i, end = " ")
# otherwise
else :
print(-1, end = " ")
# driver code
arr = [[ 1, 1, 0, 1 ],
[ 1, 1, 0, 0 ],
[ 1, 0, 0, 0 ],
[ 1, 1, 0, 1 ],
[ 0, 1, 0, 1 ]]
m = len(arr)
n = len(arr[0])
# function call
findpath(arr, m, n)
# this code is contributed by susmitakundugoaldanga.
c
// c# program for the above approach
using system;
class gfg {
// function to find the row index for
// every row of a matrix from which one
// can exit the grid after entering from left
static void findpath(int[, ] arr, int m, int n)
{
// iterate over the range [0, m-1]
for (int row = 0; row < m; row ) {
// stores the direction from
// which a person enters a cell
char dir = 'l';
// row index from which
// one enters the grid
int i = row;
// column index from which
// one enters the grid
int j = 0;
// iterate until j is atleast n-1
while (j < n) {
// if mat[i][j] is equal to 1
if (arr[i, j] == 1) {
// if entry is from left cell
if (dir == 'l') {
// decrement i by 1
i--;
// assign 'd' to dir
dir = 'd';
}
// if entry is from upper cell
else if (dir == 'u') {
// decrement j by 1
j--;
// assign 'r' to dir
dir = 'r';
}
// if entry is from right cell
else if (dir == 'r') {
// increment i by 1
i ;
// assign 'u' to dir
dir = 'u';
}
// if entry is from bottom cell
else if (dir == 'd') {
// increment j by 1
j ;
// assign 'l' to dir
dir = 'l';
}
}
// otherwise,
else {
// if entry is from left cell
if (dir == 'l') {
// increment i by 1
i ;
// assign 'u' to dir
dir = 'u';
}
// if entry is from upper cell
else if (dir == 'u') {
// increment j by 1
j ;
// assign 'l' to dir
dir = 'l';
}
// if entry is from right cell
else if (dir == 'r') {
// decrement i by 1
i--;
// assign 'd' to dir
dir = 'd';
}
// if entry is from lower cell
else if (dir == 'd') {
// decrement j by 1
j--;
// assign 'r' to dir
dir = 'r';
}
}
// if i or j is less than 0 or i is
// equal to m or j is equal to n
if (i < 0 || i == m || j < 0 || j == n)
break;
}
// if j is equal to n
if (j == n)
console.write(i " ");
// otherwise
else
console.write(-1 " ");
}
}
// driver code
public static void main()
{
// input
int[, ] arr = { { 1, 1, 0, 1 },
{ 1, 1, 0, 0 },
{ 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 1 } };
int m = arr.getlength(0);
int n = arr.getlength(1);
// function call
findpath(arr, m, n);
}
}
// this code is contributed by ukasp.
java 描述语言
output:
-1 -1 2 3 -1
时间复杂度: o(m * n)。 辅助空间: o(1)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
