동적 계획 의 로봇 주 행 격자
1843 단어 동적 계획
질문 설명:
XxY 의 격자 가 있 습 니 다. 로봇 은 격 점 만 걸 을 수 있 고 오른쪽 이나 아래로 만 걸 을 수 있 습 니 다. 왼쪽 상단 에서 오른쪽 아래 까지 걸 어야 합 니 다.로봇 이 몇 가지 방법 이 있 는 지 계산 하 는 알고리즘 을 설계 하 세 요.두 개의 정수 int 를 지정 합 니 다. x,int y 는 격자 의 크기 를 나타 내 고 로봇 의 주 법 수 를 계산한다.
사고 방향:
본 문제 에 대해 우 리 는 여전히 동태 기획 의 사상 을 운용 한다.격자 에 있 는 모든 칸 에 대해 이 칸 이 첫 줄 에 있 으 면 왼쪽 칸 으로 만 도착 할 수 있 습 니 다.칸 이 첫 번 째 열 에 있 으 면 위의 칸 에서 만 도착 할 수 있 습 니 다.격자 안의 다른 칸 은 왼쪽 칸 에서 도착 할 수도 있 고 위의 칸 에서 도착 할 수도 있다.따라서 모든 칸 에 도달 하 는 방법 수 는 왼쪽 이나 위의 칸 에 의 해 결정 된다.우 리 는 차례대로 격자 의 왼쪽 상단 에서 오른쪽 아래 까지 옮 겨 다 니 면 오른쪽 아래 칸 에 도착 하 는 방법 이 최종 결과 이다.
코드 구현:
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int x=sc.nextInt();
int y=sc.nextInt();
if(x==0||y==0)
System.out.println(0);
else if(x==1||y==1)
System.out.println(1);
else{
int [][]f=new int[x][y];
for(int j=0;j
2. 장애 가 있 는 격자
질문 설명:
제목 은 상기 와 유사 합 니 다. 다만 이번 격자 중 일부 장애 점 은 갈 수 없 음 을 주의 하 십시오. int [] [] map 는 격자 그림 을 표시 합 니 다. map [i] [j] 가 0 이면 이 점 이 장애 점 이 아니 라 장애 점 임 을 설명 합 니 다. 그렇지 않 으 면 장애 점 입 니 다.로봇 이 (0, 0) 에서 (x - 1, y - 1) 까지 의 주 법 수 를 계산 하 다.
사고 방향:
해답 을 구 하 는 사고방식 도 위의 문제 와 유사 하 다. 다만 이때 격자 에 장애 점 이 있 기 때문에 우 리 는 이렇게 고려 할 수 있다.
(1) 칸 이 장애 점 일 때 로봇 은 이 칸 에 도달 하지 못 하고 방법 수 는 0 이다.
(2) 칸 이 장애 점 이 아 닐 때 로봇 이 오른쪽으로 가 거나 아래로 내 려 가면 이 칸 에 도달 할 수 있다 는 것 을 의미한다. 따라서 이 칸 에 도달 하 는 방법 은 그 위 칸 과 왼쪽 칸 에 도달 하 는 방법의 합 이다.코드 구현:
public int countWays(int[][] map, int x, int y) {
int step[][]=new int[x][y];
if(map[0][0]==0) step[0][0]=1;
else step[0][0]=0;
for(int j=1;j
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
124. 두 갈래 나무의 최대 경로와 leetcode비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.