結果

問題 No.496 ワープクリスタル (給料日前編)
ユーザー mafuyu-aki
提出日時 2017-04-08 15:35:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 3,541 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 26,496 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-17 23:46:50
合計ジャッジ時間 931 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define READ_BUFSIZE ( 128 )
#define READ_DELIMITER ( " " )
//標準入力取得（１行）
int GetStdin( char* pszStr, int lMaxLen )
{
    int lLen = 0;
    memset( pszStr, 0, lMaxLen );
    if( fgets( pszStr, lMaxLen, stdin ) )
    {
        lLen = strlen( pszStr );
        if( lLen >= 1 )
        {
            if( pszStr[ lLen - 1 ] == 0x0A )
            {
                pszStr[ lLen - 1 ] = 0;
                lLen--;
            }
        }
    }
    
    return( lLen );
}
//標準入力を取得
//区切り文字で区切られている文字列を取り出す
//取り出した文字列のポインタをポインタ配列にセットする (数値型)
int split(char *pszStr, int lStrMax, const char *pszDelim, int *palOutList) {
    char *pszToken;
    int count = 0;
    char *pszNext_token = 0;
    int lLen = 0;
    int lNum = 0;
    memset( pszStr, 0, lStrMax );
    lLen = GetStdin( pszStr, lStrMax );
    
    if( lLen > 0 )
    {
        pszToken = strtok( pszStr, pszDelim );
        while ( pszToken != NULL ) 
        {
            *palOutList = atoi( pszToken );
            lNum++;
//          pszToken = strtok_s(NULL, pszDelim, &pszNext_token);
            pszToken = strtok( NULL, pszDelim );
            palOutList++;
        }
    }
    return lNum;
}
struct CRYSTAL
{
    int x;
    int y;
    int c;
};
int calc( int x, int y, int c, int Gx, int Gy, int F, CRYSTAL crystal[], int num, int cost )
{
    int bx = 0;
    int by = 0;
    int bc = 0;
    for( int i = 0; i < num; i++ )
    {
        if( bx == crystal[i].x && by == crystal[i].y && bc == crystal[i].c )
            break;
        bx = crystal[i].x;
        by = crystal[i].y;
        bc = crystal[i].c;
        int sum = c;
        int toho = 0;
        if ( x + crystal[i].x <=  Gx && y + crystal[i].y <= Gy )
        {
            sum += crystal[i].c;
            if( x + crystal[i].x != Gx )
                toho += F * ( Gx - ( x + crystal[i].x ) );
            if( y + crystal[i].y != Gy )
                toho += F * ( Gy - ( y + crystal[i].y ) );
            if( cost == 0 || cost > sum + toho )
                cost = sum + toho;
            if( sum < cost )
            {
                if ( x + crystal[i].x < Gx || y + crystal[i].y < Gy )
                    cost = calc( x + crystal[i].x, y + crystal[i].y, sum, Gx, Gy, F, &crystal[i+1], num-1, cost );
            }
        }
        else
        {
            if( Gx -  x > 0 )
                sum += F * ( Gx -  x );
            if( Gy -  y > 0 )
                sum += F * ( Gy -  y );
//          sum += F * ( Gx - ( x + crystal[i].x ) );
//          sum += F * ( Gy - ( y + crystal[i].y ) );
            if( cost == 0 || cost > sum )
                cost = sum;
        }
            
    }
    return cost;
}
//int型のスワップ
void swap( CRYSTAL &i, CRYSTAL &j )
{
    CRYSTAL k = i;
    i = j;
    j = k;
}
//数値配列のソート バブルソート
void sort( CRYSTAL lInput[], int lNum )
{
    for( int i = 0; i < lNum; i++ )
    {
        for( int j = lNum-1; j >= i+1; j-- )
        {
            if( lInput[ j ].x < lInput[ j-1 ].x )
                swap( lInput[j] , lInput[ j-1 ] );
        }
    }
}
int main(int argc, char *argv[]) 
{
    char szRead[READ_BUFSIZE] = "";
    //char* psOutbuf[10000] = { 0 };
    int lInput[4] = {0};
    int lLen = split( szRead, READ_BUFSIZE, READ_DELIMITER, lInput );
    int Gx = lInput[0]; //目的地X
    int Gy = lInput[1];  //目的地Y
    int N = lInput[2];  //クリスタルの数
    int F = lInput[3];  //徒歩の通行料
    CRYSTAL Crystal[200];
    memset( Crystal, 0, sizeof( Crystal ));
    for( int i = 0; i < N; i++ )
    {
         split( szRead, READ_BUFSIZE, READ_DELIMITER, lInput );
         Crystal[i].x = lInput[0];
         Crystal[i].y = lInput[1];
         Crystal[i].c = lInput[2];
    }
    //ソートする
    sort( Crystal, N );
    //全部歩いたら→(Gx+Gy)*F
    int sum = calc( 0, 0, 0, Gx, Gy, F, Crystal, N, (Gx+Gy)*F );
    printf( "%d\n", sum );
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0