동적 계획 의 로봇 주 행 격자

1843 단어 동적 계획
1. 무장 애 격자
질문 설명:
  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

좋은 웹페이지 즐겨찾기