HDU1072:Nightmare
クリックしてタイトルリンクを開く
What Are You Talking About Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/204800 K (Java/Others) Total Submission(s): 9572 Accepted Submission(s): 3001
Problem Description
Ignatius is so lucky that he met a Martian yesterday. But he didn't know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?
Input
The problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian's language. A line with a single string "END"indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian's language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can't find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(' '), tab('\t'), enter('') and all the punctuation should not be translated. A line with a single string "END"indicates the end of the book part, and that's also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.
Output
In this problem, you have to output the translation of the history book.
Sample Input
Sample Output
Author
Ignatius.L
==================================================
Ignatiusは昨夜悪夢を見た.彼は時限爆弾のある迷宮から爆弾が爆発する前に脱出しなければならない夢を見た.
1、爆弾爆発の残り時間は初期6分である.
2、Ignatiusは毎分現在位置(x,y)から(x+1,y),(x-1,y),(x,y+1),(x,y-1)のいずれかの位置に移動するしかなく、もちろん彼は国境を出ても歩けない.
壁へ.
3、迷宮の一部地域には爆弾爆発の残り時間を6分にリセットできる爆弾リセット装置があり、1つの爆弾リセット装置は何度も使用でき、使用時間は無視できる.
少しも気にしない.
4、爆弾爆発の残り時間がゼロの場合、Ignatiusがちょうど出口の位置にいても逃げられず、Ignatiusが爆弾リセット装置を手に入れても使えない.
5、入力したデジタル地図の中で:0は壁を代表し、1は空き地を代表し、2は起点を代表し、3は出口を代表し、4は爆弾リセット装置を代表する.
Ignatiusが迷路から脱出するのに要する最短時間を出力し,Ignatiusが迷路から脱出できない場合は−1を出力する.
===============================================================
BFS:BFSアルゴリズムは拡張型の探索アルゴリズムであり、「拡張」されたノードは拡張指標の最適化されたアクセスの下で得られる.
すなわち、すでにアクセスされたノードは、拡張指標にとってより優れたアクセススキームが存在しないため、アクセスされたノードは当然、重複アクセスを必要としない.
BFSの拡張指標は1つしかありません.例えば、BFSが最短ステップ数を求める場合、拡張の指標はステップ数であり、最適化はステップ数が最も短いことを指します.
しかし,本題探索の拡張指標は明らかに2つある:逃走積算時間(TCNT)と爆発残時間(TRES)である.
そしてこの2つの指標は互いに独立している:最適化とは言えないのはTCNTが最も短いことを指し、最適化とは言えないのはTRESが最も長いことを指す.
しかし,問題を考慮すると,出口の最短TCNT,すなわち出口というノードにとって最適化はTCNTの最短を指す.従ってBFSの拡張指標は選択可能である
TCNTを選択します.
一方,拡張して得られた非出口ノードについては,TCNTのみを指標とした拡張では総合指標で最適であることは保証できない.
したがって、新しいアクセススキームがTRES指標をより優れたものにすると、新しいアクセス方法は、より優れたアクセススキームである可能性がある.
したがって、この「可能な」より優れたアクセススキームを介してノードに再アクセスする必要があるのは当然である.
簡単に言えば、一般BFSの拡張条件:if(ノードがアクセスされていない)をif(ノードがアクセスされていない)に変更する
より優れている.
============================================================
What Are You Talking About Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/204800 K (Java/Others) Total Submission(s): 9572 Accepted Submission(s): 3001
Problem Description
Ignatius is so lucky that he met a Martian yesterday. But he didn't know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?
Input
The problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian's language. A line with a single string "END"indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian's language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can't find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(' '), tab('\t'), enter('') and all the punctuation should not be translated. A line with a single string "END"indicates the end of the book part, and that's also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.
Output
In this problem, you have to output the translation of the history book.
Sample Input
START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END
Sample Output
hello, i'm from mars.
i like earth!
Hint
Huge input, scanf is recommended.
Author
Ignatius.L
==================================================
Ignatiusは昨夜悪夢を見た.彼は時限爆弾のある迷宮から爆弾が爆発する前に脱出しなければならない夢を見た.
1、爆弾爆発の残り時間は初期6分である.
2、Ignatiusは毎分現在位置(x,y)から(x+1,y),(x-1,y),(x,y+1),(x,y-1)のいずれかの位置に移動するしかなく、もちろん彼は国境を出ても歩けない.
壁へ.
3、迷宮の一部地域には爆弾爆発の残り時間を6分にリセットできる爆弾リセット装置があり、1つの爆弾リセット装置は何度も使用でき、使用時間は無視できる.
少しも気にしない.
4、爆弾爆発の残り時間がゼロの場合、Ignatiusがちょうど出口の位置にいても逃げられず、Ignatiusが爆弾リセット装置を手に入れても使えない.
5、入力したデジタル地図の中で:0は壁を代表し、1は空き地を代表し、2は起点を代表し、3は出口を代表し、4は爆弾リセット装置を代表する.
Ignatiusが迷路から脱出するのに要する最短時間を出力し,Ignatiusが迷路から脱出できない場合は−1を出力する.
===============================================================
BFS:BFSアルゴリズムは拡張型の探索アルゴリズムであり、「拡張」されたノードは拡張指標の最適化されたアクセスの下で得られる.
すなわち、すでにアクセスされたノードは、拡張指標にとってより優れたアクセススキームが存在しないため、アクセスされたノードは当然、重複アクセスを必要としない.
BFSの拡張指標は1つしかありません.例えば、BFSが最短ステップ数を求める場合、拡張の指標はステップ数であり、最適化はステップ数が最も短いことを指します.
しかし,本題探索の拡張指標は明らかに2つある:逃走積算時間(TCNT)と爆発残時間(TRES)である.
そしてこの2つの指標は互いに独立している:最適化とは言えないのはTCNTが最も短いことを指し、最適化とは言えないのはTRESが最も長いことを指す.
しかし,問題を考慮すると,出口の最短TCNT,すなわち出口というノードにとって最適化はTCNTの最短を指す.従ってBFSの拡張指標は選択可能である
TCNTを選択します.
一方,拡張して得られた非出口ノードについては,TCNTのみを指標とした拡張では総合指標で最適であることは保証できない.
したがって、新しいアクセススキームがTRES指標をより優れたものにすると、新しいアクセス方法は、より優れたアクセススキームである可能性がある.
したがって、この「可能な」より優れたアクセススキームを介してノードに再アクセスする必要があるのは当然である.
簡単に言えば、一般BFSの拡張条件:if(ノードがアクセスされていない)をif(ノードがアクセスされていない)に変更する
より優れている.
============================================================
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
#define TYPE(C) map[C.x][C.y].type // C
#define TCNT(C) map[C.x][C.y].tcnt // C
#define TRES(C) map[C.x][C.y].tres // C
int T,N,M;
struct cord { int x,y; }Ori;
struct area { int type,tcnt,tres; }map[10][10];
int BFS()
{
static const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
queue<cord>q;
for(q.push(Ori);!q.empty();q.pop())
{
int n;
struct cord cur=q.front();
for(n=0;n<4;++n)
{
struct cord tmp=cur;
tmp.x+=dir[n][0];
tmp.y+=dir[n][1];
//TRES(cur)-1>TRES(tmp): TRES tmp
if(TYPE(tmp)>0&&(TCNT(tmp)==-1||TRES(cur)-1>TRES(tmp)))
{
TCNT(tmp)=TCNT(cur)+1;
TRES(tmp)=TRES(cur)-1;
if(TYPE(tmp)==3) return TCNT(tmp); //
if(TYPE(tmp)==4) TRES(tmp)=6; //
if(TRES(tmp)>=2) q.push(tmp); //TRES<2
}
}
}
return -1;
}
void initdate()
{
memset(map,-1,sizeof(map)); // -1
int i,j;
for(i=1;i<=N;++i)
{
for(j=1;j<=M;++j)
{
scanf("%d",&map[i][j].type);
if(map[i][j].type==2)
{
Ori.x=i; Ori.y=j;
map[i][j].tcnt=0;
map[i][j].tres=6;
}
}
}
}
int main()
{
while(scanf("%d",&T)==1) while(T--)
{
scanf("%d%d",&N,&M);
initdate();
printf("%d
",BFS());
}
return 0;
}