ACM02_0408 Hero

//英雄，广度优先搜索
#include "stdafx.h"
#include <stdio.h>
int mat[101][101];
int mark[101][101];
int n,m;
int sx,sy,ex,ey;
typedef struct _node{
   int x,y;
}node;

node arr[10001];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右下左上

void process()
{
   int i,j;
   int k,u;//k个spring，power is u
   int s,t,f;//s,t是队列的头和尾，f是某一层的队列的尾
   int x,y;
   int time=1;
   for(i=0;i<n;i++){
      for(j=0;j<m;j++){
         mat[i][j]=mark[i][j]=0;
      }
   }
   scanf("%d", &k);
   while(k--){
      scanf("%d %d %d",&i,&j,&u);
      i--,j--;//1位偏移
      mat[i][j]=u;
   }
   scanf("%d %d %d %d", &sx,&sy,&ex,&ey);
   sx--,sy--,ex--,ey--;//1位偏移

   s=t=0;
   arr[0].x=sx,arr[0].y=sy;
   if(sx==ex && sy==ey){
      printf("0\n");
      return;
   }
   mark[sx][sy]=1;
   while(s<=t){
      f=t;//一层遍历完 f更新一次， time更新一次
      while(s<=f){
         for(i=0;i<4;i++){
            x=arr[s].x+dir[i][0];
            y=arr[s].y+dir[i][1];
            if(0<=x && x<n && 0<=y && y<m){
               while(1){
                  if(mat[x][y]>0){
                     switch(i)
                     {
                     case 0://右
                        y=y+mat[x][y];
                        if(y>=m)y=m-1;
                        break;
                     case 1://下
                        x=x+mat[x][y];
                        if(x>=n)x=n-1;
                        break;
                     case 2://左
                        y=y-mat[x][y];
                        if(y<0)y=0;
                        break;
                     case 3://上
                        x=x-mat[x][y];
                        if(x<0)x=0;
                        break;
                     }
                  }
                  else break;
               }
               if(mark[x][y]==0){
                  mark[x][y]=1;
                  t++;
                  arr[t].x=x;
                  arr[t].y=y;
                  if(x==ex && y==ey)
                  {
                     printf("%d\n",time);
                     return;
                  }
               }
            }
         }//Four directions
         s++;//当某一点的四个方向都遍历完后,头指针就要移动了
      }//while(s<=f)
      time++;
   }
   printf("Impossible\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
   int test_case;
   int i;
   freopen("acm02_0408in.txt","r",stdin);
   freopen("acm02_0408out.txt","w",stdout);
   setbuf(stdout,NULL);
   scanf("%d", &test_case);
   for(i=0;i<test_case;i++)
   {
      scanf("%d %d",&n,&m);
      process();
   }
    return 0;
}

/* in
8
3 3
1
2 2 2
2 3
2 1
3 10
1
2 2 4
2 3
2 6
3 10
1
2 2 5
2 1
2 10
10 3
1
2 2 5
1 2
10 2
10 10
0
2 2
7 8
10 10
1
2 7 5
2 8
1 1
10 10
1
2 7 10
2 8
1 1
10 10
2
2 7 5
2 5 5
2 8
1 1
*/

/* out
1
2
4
4
11
3
2
3
*/

另外一种解法，用的存储空间多些，但是程序简洁一些。

//英雄，广度优先搜索
#include "stdafx.h"
#include <stdio.h>
int mat[100][100];
int mark[100][100];
int n,m;
int sx,sy,ex,ey;
typedef struct _node{
   int x,y;
   int s;
}node;

node arr[10000];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右下左上

void process()
{
   int i,j;
   int k,u;//k个spring，power is u
   int h,t;//h,t是队列的头和尾
   int x,y;

   for(i=0;i<n;i++){
      for(j=0;j<m;j++){
         mat[i][j]=mark[i][j]=0;
      }
   }
   scanf("%d", &k);
   while(k--){
      scanf("%d %d %d",&i,&j,&u);
      i--,j--;//1位偏移
      mat[i][j]=u;
   }
   scanf("%d %d %d %d", &sx,&sy,&ex,&ey);
   sx--,sy--,ex--,ey--;//1位偏移

   h=t=0;
   arr[0].x=sx,arr[0].y=sy,arr[0].s=0;
   if(sx==ex && sy==ey){
      printf("0\n");
      return;
   }
   mark[sx][sy]=1;
   while(h<=t){
      for(i=0;i<4;i++){
         x=arr[h].x+dir[i][0];
         y=arr[h].y+dir[i][1];
         if(0<=x && x<n && 0<=y && y<m){
            while(1){
               if(mat[x][y]>0){
                  switch(i)
                  {
                  case 0://右
                     y=y+mat[x][y];
                     if(y>=m)y=m-1;
                     break;
                  case 1://下
                     x=x+mat[x][y];
                     if(x>=n)x=n-1;
                     break;
                  case 2://左
                     y=y-mat[x][y];
                     if(y<0)y=0;
                     break;
                  case 3://上
                     x=x-mat[x][y];
                     if(x<0)x=0;
                     break;
                  }
               }
               else break;
            }
            if(mark[x][y]==0){
               mark[x][y]=1;
               t++;
               arr[t].x=x;
               arr[t].y=y;
                    arr[t].s=arr[h].s+1;
               if(x==ex && y==ey)
               {
                  printf("%d\n",arr[t].s);
                  return;
               }
            }
         }
      }//Four directions
      h++;//当某一点的四个方向都遍历完后,头指针就要移动了
   }
   printf("Impossible\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
   int test_case;
   int i;
   freopen("acm02_0408in.txt","r",stdin);
   freopen("acm02_0408out.txt","w",stdout);
   setbuf(stdout,NULL);
   scanf("%d", &test_case);
   for(i=0;i<test_case;i++)
   {
      scanf("%d %d",&n,&m);
      process();
   }
   return 0;
}