HDU 5433 Xiao Ming climbing
6957 단어 수색 하 다.Besctcoder
제목:
Xiao Ming climbing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 404 Accepted Submission(s): 93
Problem Description
Due to the curse made by the devil,Xiao Ming is stranded on a mountain and can hardly escape.
This mountain is pretty strange that its underside is a rectangle which size is
n∗m and every little part has a special coordinate
(x,y) and a height
H .
In order to escape from this mountain,Ming needs to find out the devil and beat it to clean up the curse.
At the biginning Xiao Ming has a fighting will
k ,if it turned to
0 Xiao Ming won't be able to fight with the devil,that means failure.
Ming can go to next position
(N,E,S,W) from his current position that time every step,
(abs(H1−H2))/k 's physical power is spent,and then it cost
1 point of will.
Because of the devil's strong,Ming has to find a way cost least physical power to defeat the devil.
Can you help Xiao Ming to calculate the least physical power he need to consume.
Input
The first line of the input is a single integer
T(T≤10) , indicating the number of testcases.
Then
T testcases follow.
The first line contains three integers
n,m,k ,meaning as in the title
(1≤n,m≤50,0≤k≤50) .
Then the
N ×
M matrix follows.
In matrix , the integer
H meaning the height of
(i,j) ,and '#' meaning barrier (Xiao Ming can't come to this) .
Then follow two lines,meaning Xiao Ming's coordinate
(x1,y1) and the devil's coordinate
(x2,y2) ,coordinates is not a barrier.
Output
For each testcase print a line ,if Xiao Ming can beat devil print the least physical power he need to consume,or output "
NoAnswer " otherwise.
(The result should be rounded to 2 decimal places)
Sample Input
3
4 4 5
2134
2#23
2#22
2221
1 1
3 3
4 4 7
2134
2#23
2#22
2221
1 1
3 3
4 4 50
2#34
2#23
2#22
2#21
1 1
3 3
Sample Output
1.03
0.00
No Answer
제목 의 대의:
기점 과 종점 을 정 하 다.의 념 치 k 가 있 는데 사실은 k 걸음 을 걸 을 수 있 습 니 다.한 걸음 걸 을 때마다 체력 소모 abs (a1 - a2) / x, a1, a2 는 각각 두 위치의 높이 이 고 x 는 현재 남 은 의 념 치 입 니 다.한 정 된 걸음 수 내 에서 출발점 에서 종점 까지 의 최소 체력 소 모 를 구하 세 요.
문제 풀이:
이전 코드 가 잘못 되 었 습 니 다. 슬픔 을 닦 아 주 셔 서 감사합니다.이론 적 으로 안 되 는 것 은 아니 지만 1 차원 대표 걸음 수 를 더 해 야 하기 때문에 복잡 도가 높 을 수 있다.그래서 걸음 수가 적 고 대가 가 낮은 우선 대기 열 이 BFS 에 맞 춰 져 있다 는 것 이다.
갱 점:
k = 0 일 때 시작 점 과 끝 점 이 겹 치 든 말 든 No Answer 를 직접 출력 해 야 합 니 다. 마치 문제 면 에 언급 된 것 처럼 의 념 치가 0 이면 실 패 를 의미 합 니 다.
오류 코드:
오류 원인:
새로 도착 할 때 대가 가 낮 으 면 이 점 을 갱신 하 는 것 이 아니 라 대가 가 낮 고 걸음 수가 많 으 면 도착 하지 못 하 는 상황 이 존재 할 수 있 으 며 대가 가 높 고 걸음 수가 적 으 면 도착 할 수 있다.
#include<iostream>
using namespace std;
char map[55][55];
double dp[55][55];
int n,m,k,t,sx,sy,dx,dy,dir[4][2]={-1,0,0,1,1,0,0,-1};
bool flag;
void dfs(int x,int y,int step,double cost)
{
int tx,ty;
double tcost;
if(cost>=dp[x][y])return;
else
{
dp[x][y]=cost;
if(x==dx&&y==dy)
{
flag=true;
return;
}
if(step==0)return;
for(int i=0;i<4;i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&map[tx][ty]!='#')
{
tcost=cost+1.0*abs(map[x][y]-map[tx][ty])/step;
dfs(tx,ty,step-1,tcost);
}
}
}
}
void init()
{
flag=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=1e9;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
scanf("%c",&map[i][j]);
}
scanf("%d%d%d%d",&sx,&sy,&dx,&dy);
if(k==0)
{
printf("No Answer
");
continue;
}
init();
dfs(sx,sy,k,0.0);
if(flag)
{
printf("%.2lf
",dp[dx][dy]);
}
else
printf("No Answer
");
}
return 0;
}
코드 수정:
#include <iostream>
#include <queue>
using namespace std;
char map[55][55];
double dp[55][55][55];
int n,m,k,t,sx,sy,dx,dy,dir[4][2]={-1,0,0,1,1,0,0,-1};
bool flag;
struct node
{
int x,y,step;
double cost;
bool operator<(const node &a)const
{
if(step!=a.step)
return step>a.step;
else
return cost>a.cost;
}
};
priority_queue <node> qe;
void bfs()
{
while(!qe.empty())
qe.pop();
int tx,ty,tstep;
node tmp,cur;
tmp.x=sx,tmp.y=sy,tmp.cost=0.0,tmp.step=0;
qe.push(tmp);
while(!qe.empty())
{
cur=qe.top();
qe.pop();
if(cur.cost>=dp[cur.x][cur.y][cur.step])
continue;
else
{
dp[cur.x][cur.y][cur.step]=cur.cost;
if(cur.x==dx&&cur.y==dy)
{
flag=true;
continue;
}
if(cur.step==k)
continue;
for(int i=0;i<4;i++)
{
tx=cur.x+dir[i][0];
ty=cur.y+dir[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&map[tx][ty]!='#')
{
tmp.x=tx,tmp.y=ty,tmp.step=cur.step+1;
tmp.cost=cur.cost+(1.0*abs(map[cur.x][cur.y]-map[tx][ty])/(k-cur.step));
qe.push(tmp);
}
}
}
}
}
void init()
{
flag=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int x=0;x<=k;x++)
dp[i][j][x]=1e9;
}
int main()
{
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
scanf("%c",&map[i][j]);
}
scanf("%d%d%d%d",&sx,&sy,&dx,&dy);
if(k==0)
{
printf("No Answer
");
continue;
}
init();
bfs();
if(flag)
{
ans=dp[dx][dy][0];
for(int i=1;i<=k;i++)
{
if(dp[dx][dy][i]<ans)
ans=dp[dx][dy][i];
}
printf("%.2lf
",ans);
}
else
printf("No Answer
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령 옵션 grep 명령 파일 에서 단 어 를 검색 하면 명령 은 "match pattern"을 포함 하 는 텍스트 줄 을 되 돌려 줍 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.