CSUOJ 1302 - Walking on Chessboard 暴力BFS - c++编程基础

//http://122.207.68.93/OnlineJudge/problem.php id=1302
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define oo 1000007
#define pi acos(-1.0)
#define MAXN 500005
using namespace std;  
struct node
{
      int x,y,k;
}h,p;
int m,n,k,ex,ey,num[105][105][1005];
bool used[105][105][1005];
queue myqueue;
int main()
{
      while (~scanf("%d%d%d%d%d%d%d",&n,&m,&h.x,&h.y,&ex,&ey,&k))
      {
             while (!myqueue.empty()) myqueue.pop();
             h.k=0;
             myqueue.push(h);
             memset(num,0,sizeof(num));
             memset(used,false,sizeof(used));
             used[h.y][h.x][0]=true;
             num[h.y][h.x][0]=1;
             while (!myqueue.empty())
             {
                   h=myqueue.front();
                   myqueue.pop();
                   if (h.k==k) continue;
                   if (h.y+1<=m)
                   {
                         p.x=h.x,p.y=h.y+1,p.k=h.k+1;
                         if (!used[p.y][p.x][p.k]) myqueue.push(p),used[p.y][p.x][p.k]=true;
                         num[p.y][p.x][p.k]=(num[p.y][p.x][p.k]+num[h.y][h.x][h.k])%oo;
                   }
                   if (h.x-1>




=1)
                   {
                         p.x=h.x-1,p.y=h.y,p.k=h.k+1;
                         if (!used[p.y][p.x][p.k]) myqueue.push(p),used[p.y][p.x][p.k]=true;
                         num[p.y][p.x][p.k]=(num[p.y][p.x][p.k]+num[h.y][h.x][h.k])%oo;                             
                   }
                   if (h.x+1<=n)
                   {
                         p.x=h.x+1,p.y=h.y,p.k=h.k+1;
                         if (!used[p.y][p.x][p.k]) myqueue.push(p),used[p.y][p.x][p.k]=true;
                         num[p.y][p.x][p.k]=(num[p.y][p.x][p.k]+num[h.y][h.x][h.k])%oo;                           
                   }                  
             }
             printf("%d\n",num[ey][ex][k]);
      }
      return 0;
}