csuoj 1511:欠けた碁盤

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1511
 
1511:欠けた碁盤
時間制限:1 Secメモリ制限:128 MB
タイトルの説明

 
入力
10000セット以下のデータを入力します.各データ群は、6個の整数r 1,c 1,r 2,c 2,r 3,c 3(1<=r 1,c 1,r 2,c 2,r 3,c 3<=8)を含む.3つの格子A,B,Cはそれぞれ異なることを保証する.
 
しゅつりょく
各グループのデータについて、テストポイント番号と最小ステップ数を出力します.
 
サンプル入力

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

サンプル出力

Case 1: 7
Case 2: 3

ヒント
 
ソース
湖南省第10回大学生コンピュータプログラム設計コンテスト
 
 
分析:
 
8 x 8の碁盤、BFS検索は解決でき、最初はチームメイトが条件を書き間違えてTLEを招いたが、後にデカルト座標シミュレーションを書いたが、pc^2の判定が間違っていた.後にcsuojに提出しても間違っていた.対照データに間違いは見つからなかった.orz
 
ACコード:

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<stack>
 6 #include<queue>
 7 #include<map>
 8 #include<set>
 9 #include<string.h>
10 #define ll long long 
11 #define oo 1000007
12 #define pi acos(-1.0)
13 #define MAXN 500005
14 using namespace std;   
15 struct node
16 {
17       int x,y,k;
18 }h,p;
19 int m,n,k,ex,ey,num[105][105][1005];
20 bool used[105][105][1005];
21 queue<node> myqueue; 
22 int main()
23 { 
24       while (~scanf("%d%d%d%d%d%d%d",&n,&m,&h.x,&h.y,&ex,&ey,&k))
25       {
26              while (!myqueue.empty()) myqueue.pop();
27              h.k=0;
28              myqueue.push(h);
29              memset(num,0,sizeof(num));
30              memset(used,false,sizeof(used));
31              used[h.y][h.x][0]=true;
32              num[h.y][h.x][0]=1;
33              while (!myqueue.empty())
34              {
35                    h=myqueue.front();
36                    myqueue.pop(); 
37                    if (h.k==k) continue;
38                    if (h.y+1<=m)
39                    {
40                          p.x=h.x,p.y=h.y+1,p.k=h.k+1;
41                          if (!used[p.y][p.x][p.k]) myqueue.push(p),used[p.y][p.x][p.k]=true;
42                          num[p.y][p.x][p.k]=(num[p.y][p.x][p.k]+num[h.y][h.x][h.k])%oo;
43                    }
44                    if (h.x-1>=1)
45                    {
46                          p.x=h.x-1,p.y=h.y,p.k=h.k+1;
47                          if (!used[p.y][p.x][p.k]) myqueue.push(p),used[p.y][p.x][p.k]=true;
48                          num[p.y][p.x][p.k]=(num[p.y][p.x][p.k]+num[h.y][h.x][h.k])%oo;                              
49                    }
50                    if (h.x+1<=n)
51                    {
52                          p.x=h.x+1,p.y=h.y,p.k=h.k+1;
53                          if (!used[p.y][p.x][p.k]) myqueue.push(p),used[p.y][p.x][p.k]=true;
54                          num[p.y][p.x][p.k]=(num[p.y][p.x][p.k]+num[h.y][h.x][h.k])%oo;                            
55                    }                   
56              }
57              printf("%d
",num[ey][ex][k]);
58       } 
59       return 0;
60 }

View Code
 
 
配列シミュレーション:
 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<queue>
 5 #include<iostream>
 6 #include<stack>
 7 #include<map>
 8 #include <math.h>
 9 #include<string>
10 
11 using namespace std;
12 
13 double area(double x1 , double y1 , double x2 , double y2 , double x3 , double y3)
14     {return x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x1 * y3 - x2 * y1 ;}
15 
16 int main()
17 {    
18     //freopen("i.in" , "r" , stdin);
19     //freopen("o.out" , "w" , stdout);
20     int x1 , x2 , x3 , y1 , y2 , y3 , first = 1;
21     while(~scanf("%d %d %d %d %d %d" , &x1 ,&y1 , &x2 , &y2 , &x3 , &y3))
22     if(!area(x1 , y1 , x2 , y2 , x3 , y3) && !( ((x1 == x2) && (x2 == x3) && (x1 == x3)) || (y1 == y2 && y1 == y3 && y2 == y3)) 
23         && ( (x3 > x1 && x3 < x2) || (x3 > x2 && x3 < x1))    )
24         printf("Case %d: %.0lf
" , first ++ , max(fabs(x1 - x2) , fabs(y1 - y2)) + 1 ) ; 
25     else
26         printf("Case %d: %.0lf
" , first ++ , max(fabs(x1 - x2) , fabs(y1 - y2)) ) ;
27     return 0;
28 }

View Code
 
 
他のチーム:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int x1, y1, x2, y2, x3, y3, cnt = 0;
 9     while(scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3) != EOF)
10     {
11         int res = abs(x2 - x1) > abs(y2 - y1) ? abs(x2 - x1) : abs(y2 - y1);
12         
13         if((x3 >= x1 && x3 <= x2) || (x3 <= x1 && x3 >= x2))
14         {
15                if((y1 - x1 == y2 -x2 && y1 - x1 == y3 - x3) ||(x1 + y1 == x2 + y2 && x1 + y1 == x3 + y3) || (x1 == x2 && x1 == x3) || (y1 == y2 && y1 == y3))

16                       res++;
17         }
18         printf("Case %d: %d
", ++cnt, res);
19     }
20 }

View Code
 
 
公式スケジュール:

 1 // Rujia Liu
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 #define dist(a,b) (max(abs(r[a]-r[b]),abs(c[a]-c[b])))
 8 
 9 int main() {
10   int r[3], c[3], kase = 0;
11   while(cin>>r[0]>>c[0]>>r[1]>>c[1]>>r[2]>>c[2]) {
12     int dr = abs(r[0]-r[1]);
13     int dc = abs(c[0]-c[1]);
14     int d = max(dr, dc);
15     if(dr == dc && dist(0,1) == dist(0,2) + dist(2,1)) d++;
16     printf("Case %d: %d
", ++kase, d);
17   }
18   return 0;
19 }

View Code