BJ 4485緑の服を着ている子供は最高でしょう?

22577 ワード
バックアップアルゴリズム BFS DP テキストリンク
https://www.acmicpc.net/problem/4485
これは1車両移動ごとに料金がかかり、目的地への最低料金が要求される問題です.
DPおよびBFSを用いて各セルに必要な最小距離を更新する方法と、BFSまたはDFSを用いて演算する方法がある.
これは2つのコードを記述し、それらの利点を理解できる問題です.
まず,最初のコードはDFSを用いて演算する方式である.
コードは短く、簡単に書くことができますが、各格は演算を続けるため、長い時間がかかり、問題の制限時間内に通過できません.
package day0401;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class GreenisZelda {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int[][] map;
	static int N, min;
	static int[][] dir = { { 0, 1, 0, -1 }, { 1, 0, -1, 0 } };

	static void func(int x, int y, boolean[][] b, int sum) {
		if (sum > min)
			return;
		if (sum < min && x == N - 1 && y == N - 1) {
			min = sum;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nX = x + dir[0][i];
			int nY = y + dir[1][i];
			if (nX < N && nX >= 0 && nY < N && nY >= 0 && !b[nX][nY]) {
				boolean[][] nb = new boolean[N][N];
				for (int j = 0; j < N; j++) {
					for (int k = 0; k < N; k++) {
						nb[j][k] = b[j][k];
					}
				}
				nb[nX][nY] = true;
				func(nX, nY, nb, sum + map[nX][nY]);
			}
		}

	}

	public static void main(String[] args) throws IOException {
		int tc = 0;
		while (true) {
			tc++;
			N = Integer.parseInt(br.readLine());
			if (N == 0) {
				bw.append("\n");
				break;
			}
			map = new int[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			min = -map[0][N - 1];
			for (int i = 0; i < N; i++) {
				min += map[0][i];
				min += map[i][N - 1];
			}
			func(0, 0, new boolean[N][N], map[0][0]);
			bw.append("Problem " + tc + ": " + min + "\n");
		}
		bw.flush();
	}
}
2番目のコードはDPを利用して多くの演算量を減らし,限られた時間内に通過しやすい.
package day0401;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class GreenisZeldaDP {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N, t;
	static int[][] map, dp;
	static int[][] dir = { { 0, 1, 0, -1 }, { 1, 0, -1, 0 } };


	static void BFS() {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.offer(new int[] { 0, 0 });
		dp[0][0] = map[0][0];

		while (!queue.isEmpty()) {
			int[] xy = queue.poll();
			int x = xy[0]; 
			int y = xy[1]; 

			for (int d = 0; d < 4; d++) { 
				int nx = x + dir[0][d]; 
				int ny = y + dir[1][d];

				if (nx < 0 || nx >= N || ny < 0 || ny >= N)
					continue;

				if ((dp[x][y] + map[nx][ny]) < dp[nx][ny]) {
					dp[nx][ny] = dp[x][y] + map[nx][ny];
					queue.offer(new int[] { nx, ny });
				}
			}
		}

	}

	public static void main(String[] args) throws IOException {
		int tc = 0;
		while (true) {
			tc++;
			N = Integer.parseInt(br.readLine());
			if (N == 0) {
				bw.append("\n");
				break;
			}
			map = new int[N][N];
			dp = new int[N][N];
			

			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					dp[i][j] = Integer.MAX_VALUE;
				}
			}
			BFS();
			bw.append("Problem " + tc + ": " + dp[N - 1][N - 1] + "\n");
		}
		bw.flush();
	}
}
MongooseはネストされたフィールドのObjectIdタイプを自動的に変換できません
BJ 2798ブラックジャック