USACO 5.2.1 Snail Trails 蝸牛的旅行 snail

一道簡單的題,模擬蝸牛走的路線,深搜,計算走的最多步數即可。

注意題目中說的“當 N 〉26 時,輸入文件就不能表示 Z 列以後的路障了”,這句話不用專門理他。其實就是從A的ascii碼開始向後順延,不管是什麼字母就行了。

<pre><span>USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: snail
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2856 KB]
   Test 2: TEST OK [0.000 secs, 2852 KB]
   Test 3: TEST OK [0.000 secs, 2856 KB]
   Test 4: TEST OK [0.022 secs, 2852 KB]
   Test 5: TEST OK [0.011 secs, 2856 KB]
   Test 6: TEST OK [0.011 secs, 2852 KB]
   Test 7: TEST OK [0.000 secs, 2856 KB]
   Test 8: TEST OK [0.000 secs, 2852 KB]
   Test 9: TEST OK [0.000 secs, 2856 KB]
   Test 10: TEST OK [0.000 secs, 2856 KB]
   Test 11: TEST OK [0.011 secs, 2852 KB]
   Test 12: TEST OK [0.032 secs, 2856 KB]

All tests OK.
</span>
<span>Your program ('snail') produced all correct answers!  This is your
submission #2 for this problem.  <strong>Congratulations!</strong>
</span>
</pre>
/*
ID: cmykrgb1
PROG: snail
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAX 121

using namespace std;

ifstream fi("snail.in");
ofstream fo("snail.out");

char M[MAX][MAX];
int maxstep=0;
int N,B;

void init()
{
    int i,b;
    char a;
    fi >> N >> B;
    for (i=1;i<=B;i++)
    {
        b=fi.get();
        fi >> a >> b;
        a-='A'-1;
        M[a][b]='#';
    }
}

int max(int a,int b)
{
    return a>b?a:b;
}

void dfs(int x,int y,int step)
{
    int dx,dy;
    bool r;

    for (dx=x+1,dy=y,r=false;dx<=N;dx++) //右
    {
        if (M[dx][dy]=='#')
            break;
        if (M[dx][dy]==1)
        {
            maxstep=max(maxstep,step+dx-x);
            r=true;
            break;
        }
        M[dx][dy]=1;
    }
    dx--;
    if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+dx-x);
    for (;dx>=x+1;dx--)
        M[dx][dy]=0;

    for (dx=x-1,dy=y,r=false;dx>=1;dx--) //左
    {
        if (M[dx][dy]=='#')
            break;
        if (M[dx][dy]==1)
        {
            maxstep=max(maxstep,step+x-dx);
            r=true;
            break;
        }
        M[dx][dy]=1;
    }
    dx++;
    if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+x-dx);
    for (;dx<=x-1;dx++)
        M[dx][dy]=0;

    for (dx=x,dy=y+1,r=false;dy<=N;dy++) //下
    {
        if (M[dx][dy]=='#')
            break;
        if (M[dx][dy]==1)
        {
            maxstep=max(maxstep,step+dy-y);
            r=true;
            break;
        }
        M[dx][dy]=1;
    }
    dy--;
    if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+dy-y);
    for (;dy>=y+1;dy--)
        M[dx][dy]=0;

    for (dx=x,dy=y-1,r=false;dy>=1;dy--) //上
    {
        if (M[dx][dy]=='#')
            break;
        if (M[dx][dy]==1)
        {
            maxstep=max(maxstep,step+y-dy);
            r=true;
            break;
        }
        M[dx][dy]=1;
    }
    dy++;
    if(!r && !(dx==x && dy==y)) dfs(dx,dy,step+y-dy);
    for (;dy<=y-1;dy++)
        M[dx][dy]=0;
}

void print()
{
    fo << maxstep << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    M[1][1]=1;
    dfs(1,1,0);
    print();
    return 0;
}

相關日誌