UVA_10306

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

#include
     
       #include
      
        #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; }