白準2206壁を破壊して移動
リンクテキスト
これは,既存の最短経路を探す問題で,1回で壁を破ることができるという問題である.
コアアイデアはcacheに壁を破る機会を記録することです.
最初は再帰形式のdpで解きたいだけだったが,再帰形式のbottom−up法はこの方法に適していない.目的地から出発点までの過程でブロックされるとINFを返すようにコードが実現され、以前失敗した経験がある場合はその特性によりINFが返されてエラー値が発生することを注記する.
この問題を解決するために,結果値はINF面−1に初期化され,再計算できるが,結果は繰返し演算によりタイムアウトする.エラーコードは下にあります.
一つ目は対角線巡りです.しかしこれは一般的な二次元配列ではなく実現しにくいようなので断念.
2つ目はbfsによって実現される.実現は簡単だ
ここにgreedy法があり、bfsで目的地に到達する最初の経路が最適である.同様にdeepth順にコードを回転させると,まず現れる値が最小値であることは言うまでもない.
したがって,座標が(N,M)であれば,巡視から直接離れることができる.
これは,既存の最短経路を探す問題で,1回で壁を破ることができるという問題である.
コアアイデアはcacheに壁を破る機会を記録することです.
最初は再帰形式のdpで解きたいだけだったが,再帰形式のbottom−up法はこの方法に適していない.目的地から出発点までの過程でブロックされるとINFを返すようにコードが実現され、以前失敗した経験がある場合はその特性によりINFが返されてエラー値が発生することを注記する.
この問題を解決するために,結果値はINF面−1に初期化され,再計算できるが,結果は繰返し演算によりタイムアウトする.エラーコードは下にあります.
int dp(int t, int y, int x) {
if (x == 1 && y == 1)return 1;
if (y <= 0 || x <= 0 || y > N || x > M) return 1000000001;
bool isvalid = false;
int& res = cache[t][y][x];
if (res != -1) return res;
res = 1000000000;
if (t == 1) {
if (y > 1) {
if (!visited[y - 1][x]) {
visited[y - 1][x] = true;
if (W[y - 1][x] == '0') {
res = min(res, dp(t, y - 1, x) + 1);
isvalid = true;
}
if (W[y - 1][x] == '1') {
res = min(res, dp(t - 1, y - 1, x) + 1);
isvalid = true;
}
visited[y - 1][x] = false;
}
}
if (y < N) {
if (!visited[y + 1][x]) {
visited[y + 1][x] = true;
if (W[y + 1][x] == '0') {
res = min(res, dp(t, y + 1, x) + 1);
isvalid = true;
}
if (W[y + 1][x] == '1') {
res = min(res, dp(t - 1, y + 1, x) + 1);
isvalid = true;
}
visited[y + 1][x] = false;
}
}
if (x > 1) {
if (!visited[y][x - 1]) {
visited[y][x - 1] = true;
if (W[y][x - 1] == '0') {
res = min(res, dp(t, y, x - 1) + 1);
isvalid = true;
}
if (W[y][x - 1] == '1') {
res = min(res, dp(t - 1, y, x - 1) + 1);
isvalid = true;
}
visited[y][x - 1] = false;
}
}
if (x < M) {
if (!visited[y][x + 1]) {
visited[y][x + 1] = true;
if (W[y][x + 1] == '0') {
res = min(res, dp(t, y, x + 1) + 1);
isvalid = true;
}
if (W[y][x + 1] == '1') {
res = min(res, dp(t - 1, y, x + 1) + 1);
isvalid = true;
}
visited[y][x + 1] = false;
}
}
}
else {
if (y > 1) {
if (W[y - 1][x] == '0' && !visited[y - 1][x]) {
visited[y - 1][x] = true;
res = min(res, dp(t, y - 1, x) + 1);
visited[y - 1][x] = false;
isvalid = true;
}
}
if (y < N) {
if (W[y + 1][x] == '0' && !visited[y + 1][x]) {
visited[y + 1][x] = true;
res = min(res, dp(t, y + 1, x) + 1);
visited[y + 1][x] = false;
isvalid = true;
}
}
if (x > 1) {
if (W[y][x - 1] == '0' && !visited[y][x - 1]) {
visited[y][x - 1] = true;
res = min(res, dp(t, y, x - 1) + 1);
visited[y][x - 1] = false;
isvalid = true;
}
}
if (x < M) {
if (W[y][x + 1] == '0' && !visited[y][x + 1]) {
visited[y][x + 1] = true;
res = min(res, dp(t, y, x + 1) + 1);
visited[y][x + 1] = false;
isvalid = true;
}
}
}
if(isvalid)return res;
else {
res = -1;
return 1000000001;
}
}一つ目は対角線巡りです.しかしこれは一般的な二次元配列ではなく実現しにくいようなので断念.
2つ目はbfsによって実現される.実現は簡単だ
ここにgreedy法があり、bfsで目的地に到達する最初の経路が最適である.同様にdeepth順にコードを回転させると,まず現れる値が最小値であることは言うまでもない.
したがって,座標が(N,M)であれば,巡視から直接離れることができる.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
typedef long long int ll;
struct Node {
int t, x, y;
Node(int a, int b,int c): t(a),y(b),x(c){}
};
char W[1002][1002];
bool visited[2][1002][1002];
int cache[2][1002][1002]; // 남은 벽뚫기 횟수 / 0 오른 1아래 2 왼 3 위
int N, M;
int main(void) {
cin >> N >> M;
for (int i = 0; i < 1002; i++) {
fill(W[i], W[i] + 1002, ' ');
fill(cache[0][i], cache[0][i] + 1002, 1000000000);
fill(cache[1][i], cache[1][i] + 1002, 1000000000);
fill(visited[0][i], visited[0][i] + 1002, false);
fill(visited[1][i], visited[1][i] + 1002, false);
}
cin.ignore();
for (int i = 1; i <= N; i++) {
string str;
getline(cin, str);
for (int j = 1; j <= M; j++) {
W[i][j] = str[j - 1];
}
}
cache[1][1][1] = 1;
queue<Node> q;
q.push(Node(1, 1, 1));
while (!q.empty()) {
Node tmp = q.front(); q.pop();
if (tmp.t < 0 || tmp.x<1 || tmp.y <1 || tmp.x>M || tmp.y >N || visited[tmp.t][tmp.y][tmp.x]) continue;
visited[tmp.t][tmp.y][tmp.x] = true;
int t = tmp.t, x = tmp.x, y = tmp.y;
if (tmp.x == M && tmp.y == N && cache[t][y][x] < 1000000000) break;
if (t == 1) {
if (y > 1) {
if (!visited[tmp.t][y - 1][x]) {
if (W[y - 1][x] == '0') {
cache[t][y-1][x] = min(cache[t][y - 1][x], cache[t][y][x] + 1);
q.push(Node(1, y - 1, x));
}
if (W[y - 1][x] == '1') {
cache[t- 1][y - 1][x] = min(cache[t-1][y - 1][x], cache[t][y][x] + 1);
q.push(Node(0, y - 1, x));
}
}
}
if (y < N) {
if (!visited[tmp.t][y + 1][x]) {
if (W[y + 1][x] == '0') {
cache[t][y + 1][x] = min(cache[t][y + 1][x], cache[t][y][x] + 1);
q.push(Node(1, y + 1, x));
}
if (W[y + 1][x] == '1') {
cache[t-1][y + 1][x] = min(cache[t-1][y + 1][x], cache[t][y][x] + 1);
q.push(Node(0, y + 1, x));
}
}
}
if (x > 1) {
if (!visited[tmp.t][y][x - 1]) {
if (W[y][x-1] == '0') {
cache[t][y][x-1] = min(cache[t][y][x-1], cache[t][y][x] + 1);
q.push(Node(1, y, x - 1));
}
if (W[y][x-1] == '1') {
cache[t-1][y][x-1] = min(cache[t-1][y][x-1], cache[t][y][x] + 1);
q.push(Node(0, y, x - 1));
}
}
}
if (x < M) {
if (!visited[tmp.t][y][x + 1]) {
if (W[y][x+1] == '0') {
cache[t][y][x+1] = min(cache[t][y][x+1], cache[t][y][x] + 1);
q.push(Node(1, y, x + 1));
}
if (W[y][x+1] == '1') {
cache[t-1][y][x+1] = min(cache[t-1][y][x+1], cache[t][y][x] + 1);
q.push(Node(0, y, x + 1));
}
}
}
}
else {
if (y > 1) {
if (W[y - 1][x] == '0' && !visited[tmp.t][y - 1][x]) {
cache[t][y - 1][x] = min(cache[t][y - 1][x], cache[t][y][x] + 1);
q.push(Node(0, y - 1, x));
}
}
if (y < N) {
if (W[y + 1][x] == '0' && !visited[tmp.t][y + 1][x]) {
cache[t][y + 1][x] = min(cache[t][y + 1][x], cache[t][y][x] + 1);
q.push(Node(0, y + 1, x));
}
}
if (x > 1) {
if (W[y][x - 1] == '0' && !visited[tmp.t][y][x - 1]) {
cache[t][y][x - 1] = min(cache[t][y][x - 1], cache[t][y][x] + 1);
q.push(Node(0, y, x - 1));
}
}
if (x < M) {
if (W[y][x + 1] == '0' && !visited[tmp.t][y][x + 1]) {
cache[t][y][x + 1] = min(cache[t][y][x + 1], cache[t][y][x] + 1);
q.push(Node(0, y, x + 1));
}
}
}
}
int res = min(cache[0][N][M], cache[1][N][M]);
if (res >= 1000000000) res = -1;
cout << res << endl;
return 0;
}Reference
この問題について(白準2206壁を破壊して移動), 我々は、より多くの情報をここで見つけました https://velog.io/@reljacer/백준-2206-벽-부수고-이동하기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol