car.cpp

使用动态规划算法求解汽车加油问题

# include <FSTREAM.H>    
   
//# define MCOST 0xffffffff      
typedef unsigned long ulong;   
   
   
void writeData(ulong cost);   
ulong minpCost(int x, int y);   
ulong minppCost(int x1, int y1, int x2, int y2);   
void p2p(int x1, int y1, int x2, int y2);   
void pp2p(int x1, int y1, int x2, int y2, int x3, int y3);   
void renewUp(int x, int y);   
void renewDown(int x, int y);   
void renewLeft(int x, int y);   
void renewRight(int x, int y);   
   
   
int N, K, A, B, C;   
int level = 2;  //起始层为起点    
ulong MCOST = 0xffffffff;    
ulong cost[102][102][12];   
int pos[102][102];  //存放加油站位置信息    
   
   
int main(){   
   
    ifstream infile("input.txt");   
    if (!infile){   
        cout << "无法打开input.txt\n";   
        return -1;   
    }   
    infile >> N >> K >> A >> B >> C;   
   
    //异常处理    
    if ( (N < 2) || (N > 100) || (K < 2) || (K > 10) || (A < 0) || (B < 0) || (C < 0) ){   
        cout << "输入数据有误\n";   
        return -1;   
    }   
   
    //正常处理    
    int ia, ib, ic;   
    for (ia = 1; ia <= N; ia++){   
        for (ib = 1; ib <= N; ib++){   
            infile >> pos[ib][ia];   
        }   
    }   
    infile.close();   
   
    for (ia = 1; ia <= N; ia++){   
        for (ib = 1; ib <= N; ib++){   
            for (ic = 1; ic <= K; ic++)   
                cost[ia][ib][ic] = MCOST;   
        }   
    }   
   
    cost[1][1][K] = 0;  //起点费用为0    
   
    for (level = 3; level <= N + 1; level++){  //处理上三角范围,含对角线level=N+1    
        p2p(level - 2, 1, level - 1, 1);  //向y轴正向推进    
        p2p(1, level - 2, 1, level - 1);  //向x轴正向推进    
        for (int id = level - 2; id >= 2; id--){   
            pp2p(id - 1, level - id, id, level - id - 1, id, level - id);  //(id, level-id)点的左点和上点来更新    
            //从(id, level-id)开始倒退更新其余的点    
            renewUp(id, level - id - 1);   
            renewLeft(id - 1, level - id);   
        }   
    }   
   
    for (level = N + 2; level <= 2 * N - 1; level++){ //处理下三角范围,不含对角线    
        for (int id = level - N; id <= N; id++){   
            pp2p(id - 1, level - id, id, level - id - 1, id, level - id);  //(id, level-id)点的左点和上点来更新    
            //从(id, level-id)开始倒退更新其余的点    
            renewUp(id, level - id - 1);   
            renewLeft(id - 1, level - id);   
   
        }   
    }   
   
    ulong mincost = minppCost(N, N - 1, N - 1, N);  //最后两个点的最小费用就是到终点的最小费用    
    writeData(mincost);   
   
    return 0;   
}   
   
   
   
void writeData(ulong cost){   
    ofstream outf("output.txt");   
    if (!outf)   
        cout << "无法打开文件output.txt\n";   
    else{   
        cout << "最小费用是" << cost << endl;   
        outf << cost;   
    }   
    outf.close();   
}   
   
   
ulong minpCost(int x, int y){   
    ulong mincost = MCOST;   
    for (int ir = 1; ir <= K; ir++)   
        if (cost[x][y][ir] < mincost)   
            mincost = cost[x][y][ir];   
    //如果mincost = MCOST则可能有异常    
    return mincost;   
}   
   
ulong minppCost(int x1, int y1, int x2, int y2){   
    ulong mc1 = minpCost(x1, y1);   
    ulong mc2 = minpCost(x2, y2);   
    return ( (mc1 < mc2) ? mc1 : mc2);   
}   
   
void p2p(int x1, int y1, int x2, int y2){   
    if (pos[x2][y2] == 0){ //不是加油站    
        for (int ir = 2; ir <= K; ir++){   
            if (cost[x1][y1][ir] == MCOST)  //没有改进    
                continue;   
            else   
                cost[x2][y2][ir - 1] = cost[x1][y1][ir];   
        }   
        if (cost[x1][y1][1] != MCOST)   
            //设油库并加油    
            cost[x2][y2][K] = cost[x1][y1][1] + C + A;   
    }   
    else //(x2, y2)为加油站    
        cost[x2][y2][K] = minpCost(x1, y1) + A;   
}   
   
void pp2p(int x1, int y1, int x2, int y2, int x3, int y3){   
    if (pos[x3][y3] == 0){ //非加油站    
        for (int ir = 2; ir <= K; ir++)   
            if ((cost[x1][y1][ir] == MCOST) && (cost[x2][y2][ir] == MCOST))   
                continue;   
            else   
                cost[x3][y3][ir - 1] = (cost[x1][y1][ir] < cost[x2][y2][ir]) ? cost[x1][y1][ir] : cost[x2][y2][ir];   
        cost[x3][y3][K] = (cost[x1][y1][1] < cost[x2][y2][1]) ? cost[x1][y1][1] : cost[x2][y2][1];   
        if (cost[x3][y3][K] != MCOST)   
            cost[x3][y3][K] += C + A;   
    }   
    else{ //是加油站    
        cost[x3][y3][K] = minppCost(x1, y1, x2, y2) + A;   
    }   
}   
   
void renewUp(int x, int y){ //从下向上, (x,y)为被更新的点    
    if (y == 0) return;  //防止出界    
    bool isUpdate = false;   
    if (pos[x][y] == 0){ //非加油站    
        for (int ir = 2; ir <= K; ir++)   
            if (cost[x][y + 1][ir] == MCOST)   
                continue;   
            else   
                if (cost[x][y][ir - 1] > cost[x][y + 1][ir] + B){   
                    cost[x][y][ir - 1] = cost[x][y + 1][ir] + B;   
                    isUpdate = true;   
                }   
        if ( (cost[x][y + 1][1] != MCOST) &&    
            (cost[x][y][K] > cost[x][y + 1][1] + A + B + C ) ){   
             cost[x][y][K] = cost[x][y + 1][1] + A + B + C;   
             isUpdate = true;   
        }   
    }   
    else{  //是加油站    
        ulong tmp = minpCost(x, y + 1) + A + B;   
        if (cost[x][y][K] > tmp){   
            cost[x][y][K] = tmp;   
            isUpdate = true;   
        }   
    }   
    if ( !isUpdate ) return; //无任何更新则返回    
    renewUp(x, y - 1);   
    renewLeft(x - 1, y);   
    renewRight(x + 1, y);   
}   
   
void renewDown(int x, int y){ //从上向下, (x,y)为被更新的点    
    if (x + y > level) return;  //在已搜索过的上三角范围内更新    
    bool isUpdate = false;   
    if (pos[x][y] == 0){ //非加油站    
        for (int ir = 2; ir <= K; ir++)   
            if (cost[x][y - 1][ir] == MCOST)   
                continue;   
            else   
                if (cost[x][y][ir - 1] > cost[x][y - 1][ir]){   
                    cost[x][y][ir - 1] = cost[x][y - 1][ir];   
                    isUpdate = true;   
                }   
        if ( (cost[x][y - 1][1] != MCOST) &&    
            (cost[x][y][K] > cost[x][y - 1][1] + A + C ) ){   
             cost[x][y][K] = cost[x][y - 1][1] + A + C;   
             isUpdate = true;   
        }   
    }   
    else{  //是加油站    
        ulong tmp = minpCost(x, y - 1) + A;   
        if (cost[x][y][K] > tmp){   
            cost[x][y][K] = tmp;   
            isUpdate = true;   
        }   
    }   
    if ( !isUpdate ) return; //无任何更新则返回    
    renewDown(x, y + 1);   
    renewLeft(x - 1, y);   
    renewRight(x + 1, y);   
}   
   
void renewLeft(int x, int y){ //从右向左, (x,y)为被更新的点    
    if (x == 0) return;  //防止出界    
    bool isUpdate = false;   
    if (pos[x][y] == 0){ //非加油站    
        for (int ir = 2; ir <= K; ir++)   
            if (cost[x + 1][y][ir] == MCOST)   
                continue;   
            else   
                if (cost[x][y][ir - 1] > cost[x + 1][y][ir] + B){   
                    cost[x][y][ir - 1] = cost[x + 1][y][ir] + B;   
                    isUpdate = true;   
                }   
        if ( (cost[x + 1][y][1] != MCOST) &&    
            (cost[x][y][K] > cost[x + 1][y][1] + A + B + C ) ){   
             cost[x][y][K] = cost[x + 1][y][1] + A + B + C;   
             isUpdate = true;   
        }   
    }   
    else{  //是加油站    
        ulong tmp = minpCost(x + 1, y) + A + B;   
        if (cost[x][y][K] > tmp){   
            cost[x][y][K] = tmp;   
            isUpdate = true;   
        }   
    }   
    if ( !isUpdate ) return; //无任何更新则返回    
    renewUp(x, y - 1);   
    renewDown(x, y + 1);   
    renewLeft(x - 1, y);   
}   
   
void renewRight(int x, int y){ //从左向右, (x,y)为被更新的点    
    if (x + y > level) return; //在已搜索过的上三角范围内更新    
    bool isUpdate = false;   
    if (pos[x][y] == 0){ //非加油站    
        for (int ir = 2; ir <= K; ir++)   
            if (cost[x - 1][y][ir] == MCOST)   
                continue;   
            else   
                if (cost[x][y][ir - 1] > cost[x - 1][y][ir]){   
                    cost[x][y][ir - 1] = cost[x - 1][y][ir];   
                    isUpdate = true;   
                }   
        if ( (cost[x - 1][y][1] != MCOST) &&    
            (cost[x][y][K] > cost[x - 1][y][1] + A + C ) ){   
             cost[x][y][K] = cost[x - 1][y][1] + A + C;   
             isUpdate = true;   
        }   
    }   
    else{  //是加油站    
        ulong tmp = minpCost(x - 1, y) + A;   
        if (cost[x][y][K] > tmp){   
            cost[x][y][K] = tmp;   
            isUpdate = true;   
        }   
    }   
    if ( !isUpdate ) return; //无任何更新则返回    
    renewUp(x, y - 1);   
    renewDown(x, y + 1);   
    renewRight(x + 1, y);   
}