哈理工oj-1440-殘缺的棋盤【BFS】

​

1440: 殘缺的棋盤

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 196  

Solved: 55

[

​​Submit​​][

​​Status​​][

​​Web Board​​]

Description

在國際象棋裡，王是最重要的一個棋子。每一步，王可以往上下左右或者對角線方向移動一步，如下圖所示。

給定兩個格子A(r1,c1), B(r2,c2)，你的任務是計算出一個王從A到B至少需要走多少步。為了避免題目太簡單，我們從棋盤裡拿掉了一個格子C(r3,c3)（ABC保證互不相同），要求王從A走到B的過程中不能進入格子C。在本題中，各行從上到下編号為1~8，各列從左到右編号為1~8。

Input

輸入包含不超過

10000

組資料。每組資料包含

6

個整數

r1, c1, r2, c2, r3, c3 (1<=r1, c1, r2, c2, r3, c3<=8).

三個格子

A, B, C

保證各不相同。

Output

對于每組資料，輸出測試點編号和最少步數。

Sample Input

1 1 8 7 5 6
1 1 3 3 2 2      

Sample Output

Case 1: 7
Case 2: 3      

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int r1,r2,r3,c1,c2,c3;
int dx[]={-1,0,1,0,-1,-1,1,1};
int dy[]={0,-1,0,1,-1,1,-1,1};
bool vis[10][10];
int ans;
struct node
{
  int x,y,step;
};
bool judge(int a,int b)
{
  if(a<1||b<1||a>8||b>8||vis[a][b])
    return 0;
  return 1;
}
int bfs(int a,int b)
{
  node now,next;
  now.x=a; now.y=b; now.step=0;
  vis[a][b]=1;
  vis[r3][c3]=1;
  queue<node> Q;
  while(!Q.empty())  Q.pop();
  Q.push(now);
  while(!Q.empty())
  {
    now=Q.front();
    Q.pop();
    if(now.x==r2&&now.y==c2)
      return now.step;
    /*
    if(now.x==r2&&now.y==c2)
    {
      printf("%d\n",now.step);
      return ;
    }
    */
    for(int i=0;i<8;i++)
    {
      next.x=now.x+dx[i];
      next.y=now.y+dy[i];
      if(judge(next.x,next.y))
      {
        vis[next.x][next.y]=1;
        next.step=now.step+1;
        Q.push(next);
      }
    }
  }
}
int main()
{
  int text=0;
  while(~scanf("%d%d%d%d%d%d",&r1,&c1,&r2,&c2,&r3,&c3))
  {
    memset(vis,0,sizeof(vis));
    printf("Case %d: %d\n",++text,bfs(r1,c1));
  }
  return 0;
}