白準-17070号パイプ移動1

3160 ワード
テキストリンク
https://www.acmicpc.net/problem/17070

以前のパイプの状態に応じて、次の3種類が選択できます.

方法


ケース数を計算したBFSに近いが,ほとんどがDPで解決されているようである.TODO DPで解いてみるべきかもしれません.
  • 端点座標に基づいてBFSナビゲーションを行い、Pipeクラスを作成して古いパイプタイプ
    • を取得する.
  • curTypeの値により3種類に分けられ、該当する場合はキュー
    • に入れる.
  • 現在の座標が終点である場合には応答値が増加し、そうである場合には
    • を参照する.
    開始点が1の場合、無条件は不可、出力0はに戻る.

    ソース

    import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int[][] Array;
	static int Answer = 0;
	static int[][] Dir = {{0,1}, {1,1},{1,0}}; //가로는 0, 1 / 대각선은 0, 1, 2 / 세로는 1, 2
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Array = new int[N][N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				Array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		if(Array[N-1][N-1] == 1) {
			System.out.println(0);
			return;
		}
		
		Queue<Pipe> q = new LinkedList<Pipe>();
		q.offer(new Pipe(0, 1, 0)); // (0, 1) 좌표에 가로로 놓임
		
		while(!q.isEmpty()) {
			Pipe curPipe = q.poll();
			int curX = curPipe.x;
			int curY = curPipe.y;
			if(curX == N-1 && curY == N-1) {
				Answer++;
				continue;
			}
			int curType = curPipe.type;
			
			for(int i = 0; i < Dir.length; i++) {
				 int nextX = curX + Dir[i][0];
				 int nextY = curY + Dir[i][1];
				 
				 if(nextX >= N || nextY >= N || Array[nextX][nextY] == 1) continue; //범위밖은 무조건 아웃
				 
				 if(curType == 0) {
					 if(i == 0) q.offer(new Pipe(nextX, nextY, 0));
					 else if(i == 1 && Array[curX][curY+1] == 0 && Array[curX+1][curY+1] == 0 && Array[curX+1][curY] == 0) {
						 q.offer(new Pipe(nextX, nextY, 1));
					 }
					 
				 } else if(curType == 1) {
					 if(i == 0) q.offer(new Pipe(nextX, nextY, 0));
					 else if(i == 1 && Array[curX][curY+1] == 0 && Array[curX+1][curY+1] == 0 && Array[curX+1][curY] == 0) {
						 q.offer(new Pipe(nextX, nextY, 1));
					 } else if(i == 2) q.offer(new Pipe(nextX, nextY, 2));
				 } else {
					if(i == 1 && Array[curX][curY+1] == 0 && Array[curX+1][curY+1] == 0 && Array[curX+1][curY] == 0) {
						 q.offer(new Pipe(nextX, nextY, 1));
					 } else if(i == 2) q.offer(new Pipe(nextX, nextY, 2)); 
				 }	 
			}
		}
		System.out.println(Answer);
	}

}
class Pipe{
	int x;
	int y;
	int type; // 가로 0,대각선 1, 세로 2
	
	Pipe(int x, int y, int type) {
		this.x = x;
		this.y = y;
		this.type = type;
	}
}
    Python基礎学習day 7|テストコード
    [JavaScript]変数