学步园

UVA_10306

    直接将x、y由小到大进行递推即可，对每个格子都尝试一下M个向量加法操作。

#include<stdio.h>
#include<string.h>
#define MAXM 50
#define MAXS 310
#define INF 1000000000
int M, S, x[MAXM], y[MAXM], f[MAXS][MAXS];
void init()
{
int i;
    scanf("%d%d", &M, &S);
for(i = 0; i < M; i ++)
        scanf("%d%d", &x[i], &y[i]);
}
void solve()
{
int i, j, k, newx, newy, min;
    min = INF;
for(i = 0; i <= S; i ++)
for(j = 0; j <= S; j ++)
            f[i][j] = INF;
    f[0][0] = 0;
for(i = 0; i <= S; i ++)
for(j = 0; j <= S; j ++)
if(f[i][j] != INF)
            {
if(i * i + j * j == S * S && f[i][j] < min)
                {
                    min = f[i][j];
continue;
                }
for(k = 0; k < M; k ++)
                {
                    newx = i + x[k];
                    newy = j + y[k];
if(newx <= S && newy <= S && f[i][j] + 1 < f[newx][newy])
                        f[newx][newy] = f[i][j] + 1;
                }
            }
if(min == INF)
        printf("not possible\n");
else
        printf("%d\n", min);
}
int main()
{
int t;
    scanf("%d", &t);
while(t --)
    {
        init();
        solve();
    }
return 0;
}