杭電2128 Tempter of the Bone II(広捜)bfs+優先キュー+伴うmap
Tempter of the Bone II
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 98304/32768 K (Java/Others) Total Submission(s): 1960 Accepted Submission(s): 510
Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze was changed and the way he came in was lost.He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with the sizes of N by M. The maze is made up of a door,many walls and many explosives. Doggie need to reach the door to escape from the tempter. In every second, he could move one block to one of the upper, lower, left or right neighboring blocks. And if the destination is a wall, Doggie need another second explode and a explosive to explode it if he had some explosives. Once he entered a block with explosives,he can take away all of the explosives. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains two integers N, M,(2 <= N, M <= 8). which denote the sizes of the maze.The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall;
'S': the start point of the doggie;
'D': the Door;
'.': an empty block;
'1'--'9':explosives in that block.
Note,initially he had no explosives.
The input is terminated with two 0's. This test case is not to be processed.
Output
For each test case, print the minimum time the doggie need to escape if the doggie can survive, or -1 otherwise.
Sample Input
Sample Output
Author
XHD
无力吐槽………………………………………
ここでまず大牛からもらったデータを見てみましょう.読者のバグ探しに役立つことを望んでいます.
データソース:http://blog.csdn.net/mnlm1991/article/details/5919971
6 6 S1XX3X XXXXXX 2XXXXX XXXXXX XXXXXX X1XDXX 29
5 3 S.. 1X. XX. ... XXD
6
5 6 S.XXXX 21..XX XXXXXX XXXXXX 3XXXDX
11
6 5
S.XX1
X.1X1
XX.X.
XXXXX
XXXXX
XXXDX
この問題に対して本当にツッコミを入れる力がなくて、この問題はいくつかの難点があります:
1.vis配列は通常の2次元配列ではありません
2.元の地図でXを爆破することはできません.構造体でmapを伴う必要があります
3.優先キューを使用して、Xを爆破する方法はたくさんあります.優先キューの特性を借りて問題を完成しなければなりません.
考えがはっきりしていて、爆弾に出会ったらポケットに入れて、それから爆弾の場所は‘.’になって、‘.’に出会ったら直接歩いて行って、‘X’に出会ったら爆発します(なければ爆発しません)
構想は簡単だが、コードの実現は穴に満ちていて、いろいろな穴がある.大きな穴.
くだらないことはくどくどしないで、ここは直接コードをつけます:
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 98304/32768 K (Java/Others) Total Submission(s): 1960 Accepted Submission(s): 510
Problem Description
The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze was changed and the way he came in was lost.He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with the sizes of N by M. The maze is made up of a door,many walls and many explosives. Doggie need to reach the door to escape from the tempter. In every second, he could move one block to one of the upper, lower, left or right neighboring blocks. And if the destination is a wall, Doggie need another second explode and a explosive to explode it if he had some explosives. Once he entered a block with explosives,he can take away all of the explosives. Can the poor doggie survive? Please help him.
Input
The input consists of multiple test cases. The first line of each test case contains two integers N, M,(2 <= N, M <= 8). which denote the sizes of the maze.The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall;
'S': the start point of the doggie;
'D': the Door;
'.': an empty block;
'1'--'9':explosives in that block.
Note,initially he had no explosives.
The input is terminated with two 0's. This test case is not to be processed.
Output
For each test case, print the minimum time the doggie need to escape if the doggie can survive, or -1 otherwise.
Sample Input
4 4
SX..
XX..
....
1..D
4 4
S.X1
....
..XX
..XD
0 0
Sample Output
-1
9
Author
XHD
无力吐槽………………………………………
ここでまず大牛からもらったデータを見てみましょう.読者のバグ探しに役立つことを望んでいます.
データソース:http://blog.csdn.net/mnlm1991/article/details/5919971
6 6 S1XX3X XXXXXX 2XXXXX XXXXXX XXXXXX X1XDXX 29
5 3 S.. 1X. XX. ... XXD
6
5 6 S.XXXX 21..XX XXXXXX XXXXXX 3XXXDX
11
6 5
S.XX1
X.1X1
XX.X.
XXXXX
XXXXX
XXXDX
この問題に対して本当にツッコミを入れる力がなくて、この問題はいくつかの難点があります:
1.vis配列は通常の2次元配列ではありません
2.元の地図でXを爆破することはできません.構造体でmapを伴う必要があります
3.優先キューを使用して、Xを爆破する方法はたくさんあります.優先キューの特性を借りて問題を完成しなければなりません.
考えがはっきりしていて、爆弾に出会ったらポケットに入れて、それから爆弾の場所は‘.’になって、‘.’に出会ったら直接歩いて行って、‘X’に出会ったら爆発します(なければ爆発しません)
構想は簡単だが、コードの実現は穴に満ちていて、いろいろな穴がある.大きな穴.
くだらないことはくどくどしないで、ここは直接コードをつけます:
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
struct node
{
int x,y,num,step;
char mp[15][15];// map（ X）
bool friend operator<(node a,node b)
{
return a.step>b.step;
}
} t;
int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
char s[15][15];
int vis[15][15][55];
int n,m,ex,ey,flag;
int bfs(int x,int y)
{
priority_queue<node>q;
int i,j;
for(i=0; i<n; i++)
for(j=0; j<m; j++)
t.mp[i][j]=s[i][j];// copy
t.step=0;
t.num=0;
t.x=x;
t.y=y;
vis[t.x][t.y][0]++;
q.push(t);
while(!q.empty())
{
t=q.top();
if(t.x==ex && t.y==ey)
return t.step;
for(i=0; i<4; i++)// .
{
t.step++;
t.x+=dir[i][1];
t.y+=dir[i][0];
if(t.x>=0 && t.x<n && t.y>=0 && t.y<m && vis[t.x][t.y][t.num]<100)// 100
{
if(t.mp[t.x][t.y]=='.')
{
vis[t.x][t.y][t.num]++;
q.push(t);
}
else if(t.mp[t.x][t.y]=='X' && t.num>0)
{
vis[t.x][t.y][t.num]++;
t.step++;
t.num--;
t.mp[t.x][t.y]='.';
q.push(t);
}
else if(t.mp[t.x][t.y]>='1' && t.mp[t.x][t.y]<='9')
{
vis[t.x][t.y][t.num]++;
t.num+=t.mp[t.x][t.y]-'0';
t.mp[t.x][t.y]='.';
q.push(t);
}
}
t=q.top();
}
q.pop();
}
return -1;
}
int main()
{
int i,j,x1,y1;
while(~scanf("%d%d",&n,&m) && n)
{
for(i=0; i<n; i++)
scanf("%s",s[i]);
for(i=0; i<n; i++)
for(j=0; j<m; j++)
{
if(s[i][j]=='S')
{
s[i][j]='.';
x1=i,y1=j;
}
else if(s[i][j]=='D')
{
s[i][j]='.';
ex=i,ey=j;
}
}
memset(vis,0,sizeof vis);
printf("%d
",bfs(x1,y1));
}
}