CSU_1511_殘缺的棋盤

殘缺的棋盤

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 604   Solved: 215

[ Submit][ Status][ Web Board]

Description

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      

HINT

水題，看到最短路，然後bfs

但是這個題目不用bfs也可以做

因為隻挖掉了棋盤上的一個點

是以不是出現在一個斜線上起點   坑   終點

那麼都不會影響最短步數

出現那種情況則需要多走一步

不過如果扣掉格子不止一個，那麼bfs還是必要的

機智法

#include <iostream>
#include <stdio.h>
using namespace std;
 
const int M=10;
 
int main()
{
    int r1,c1,r2,c2,r3,c3;
    int ca=1;
    while(scanf("%d%d%d%d%d%d",&r1,&c1,&r2,&c2,&r3,&c3)!=EOF)
    {
        if(c1-c2==r1-r2&&c1-c3==r1-r3&&(r3>min(r1,r2))&&(r3<max(r1,r2)))
        {
            printf("Case %d: %d\n",ca++,max(r1,r2)-min(r1,r2)+1);
            continue;
        }
        if(c1-c2==r2-r1&&c1-c3==r3-r1&&(r3>min(r1,r2))&&(r3<max(r1,r2)))
        {
            printf("Case %d: %d\n",ca++,max(r1,r2)-min(r1,r2)+1);
            continue;
        }
        int ans=max(max(r1,r2)-min(r1,r2),max(c1,c2)-min(c1,c2));
        printf("Case %d: %d\n",ca++,ans);
    }
    return 0;
}
           

bfs

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
 
const int M=10;
 
int ti[M][M];
 
queue <int> re;
 
int dx[]={0,0,1,-1,1,1,-1,-1};
int dy[]={1,-1,0,0,1,-1,1,-1};
 
int bfs(int stx,int sty,int edx,int edy)
{
    while(!re.empty())
        re.pop();
    re.push(stx+sty*M);
    ti[stx][sty]=1;
    while(!re.empty())
    {
        int t=re.front();
        re.pop();
        int tx=t%M,ty=t/M;
        for(int i=0;i<8;i++)
        {
            int x=tx+dx[i],y=ty+dy[i];
            if(ti[x][y])
                continue;
            if(x<=0||y<=0||x>8||y>8)
                continue;
            if(x==edx&&y==edy)
            {
                return ti[tx][ty];
            }
            ti[x][y]=ti[tx][ty]+1;
            re.push(x+y*M);
        }
    }
}
 
int main()
{
    int r1,c1,r2,c2,r3,c3;
    int ca=1;
    while(scanf("%d%d%d%d%d%d",&r1,&c1,&r2,&c2,&r3,&c3)!=EOF)
    {
        memset(ti,0,sizeof(ti));
        ti[r3][c3]=100;
        printf("Case %d: %d\n",ca++,bfs(r1,c1,r2,c2));
    }
    return 0;
}