我正在尝试在Timus Online Judge上解决问题http://acm.timus.ru/problem.aspx?space=1&num=1119
但是,由于某些奇怪的原因,递归函数不起作用。如果我只打印返回的最终值,则会打印:“ -nan”。当我打印其四舍五入的形式时,它会打印一个垃圾值。

#include <iostream>
#include <cstring>
#include <cmath>
#define min(x,y) ((x<y) ? (x) : (y))
using namespace std;
int x,y;
float dp[1001][1001];    //for memoization
bool d[1001][1001];      // for storing whether diagonal movement is possible or not
float solve(int x,int y) {
    if (dp[x][y]!= -1.0)
        return dp[x][y];
    if (x == 0 && y == 0)
        return (dp[x][y] = 0.0);
    if (x == 0 )
        return (dp[x][y] = y*100);
    if (y == 0)
        return (dp[x][y] = x*100);
    float ret;
    float r1,r2,r3;
    r1 = 100.0 + solve(x-1,y);
    r2 = 100.0 + solve(x,y-1);
    ret = min(r1,r2);
    if (d[x][y]) {
        r3 = solve(x-1,y-1);
        r3 = r3 + 141.42;
        ret = min(ret,r3);
    }
    dp[x][y] = ret;
    return ret;
}
int main() {
    cin >> x >> y;
    int k;
    int d1,d2;
    cin >> k;
    memset(dp,-1.0,sizeof dp);
    memset(d,false,sizeof d);
    for (int i=0;i<k;i++) {
        cin >> d1 >> d2;
        d[d1][d2]=true;
    }
    float dist = solve(x,y);
    int ans = dist;
    if (dist - ans > 0.5) {
        ans++;
    }
    cout << ans << endl;    // Prints a garbage value
}                           // cout << dist << endl prints "-nan"


这是ideone链接:http://ideone.com/6C2WjR

最佳答案

memset(dp,-1.0,sizeof dp);并没有您的想法,请改用std::fillstd::fill_n

或者只是std::vector

std::vector<std::vector<float>> dp(1001, std::vector<float>(1001, -1.f));

10-08 13:45