csuoj 1511: 残缺的棋盘

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1511

1511: 残缺的棋盘

时间限制: 1 Sec  内存限制: 128 MB

题目描述

输入

输入包含不超过10000 组数据。每组数据包含6个整数r1, c1, r2, c2, r3, c3 (1<=r1, c1, r2, c2, r3, c3<=8). 三个格子A, B, C保证各不相同。

输出

对于每组数据，输出测试点编号和最少步数。

样例输入

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

样例输出

Case 1: 7
Case 2: 3

提示

来源

湖南省第十届大学生计算机程序设计竞赛

分析：

8 x 8 的棋盘，BFS搜索可以解决，一开始队友写错了条件导致TLE ， 后来又写了一个笛卡尔坐标模拟的，但是pc^2判错啦 ， 后来在csuoj上提交也是错的，对照数据没有发现错误，真是无语啦，把其他队的AC代码提交到csuoj上也是WA，真是服了，但是搜索做的都过啦，，，orz

AC代码：

 #include<iostream>
 #include<stdio.h>
 #include<cmath>
 #include<algorithm>
 #include<stack>
 #include<queue>
 #include<map>
 #include<set>
 #include<string.h>
 #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[][][];
 bool used[][][];
 queue<node> 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=;
              myqueue.push(h);
              memset(num,,sizeof(num));
              memset(used,false,sizeof(used));
              used[h.y][h.x][]=true;
              num[h.y][h.x][]=;
              while (!myqueue.empty())
              {
                    h=myqueue.front();
                    myqueue.pop();
                    if (h.k==k) continue;
                    if (h.y+<=m)
                    {
                          p.x=h.x,p.y=h.y+,p.k=h.k+;
                          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->=)
                    {
                          p.x=h.x-,p.y=h.y,p.k=h.k+;
                          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+<=n)
                    {
                          p.x=h.x+,p.y=h.y,p.k=h.k+;
                          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 ;
 }

数组模拟：

 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<queue>
 #include<iostream>
 #include<stack>
 #include<map>
 #include <math.h>
 #include<string>

 using namespace std;

 double area(double x1 , double y1 , double x2 , double y2 , double x3 , double y3)
     {return x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x1 * y3 - x2 * y1 ;}

 int main()
 {
     //freopen("i.in" , "r" , stdin);
     //freopen("o.out" , "w" , stdout);
     int x1 , x2 , x3 , y1 , y2 , y3 , first = ;
     while(~scanf("%d %d %d %d %d %d" , &x1 ,&y1 , &x2 , &y2 , &x3 , &y3))
     if(!area(x1 , y1 , x2 , y2 , x3 , y3) && !( ((x1 == x2) && (x2 == x3) && (x1 == x3)) || (y1 == y2 && y1 == y3 && y2 == y3))
         && ( (x3 > x1 && x3 < x2) || (x3 > x2 && x3 < x1))    )
         printf("Case %d: %.0lf\n" , first ++ , max(fabs(x1 - x2) , fabs(y1 - y2)) +  ) ;
     else
         printf("Case %d: %.0lf\n" , first ++ , max(fabs(x1 - x2) , fabs(y1 - y2)) ) ;
     return ;
 }

其他队的：

 #include <iostream>
 #include <cstdio>
 #include <cmath>
 using namespace std;

 int main()
 {
     int x1, y1, x2, y2, x3, y3, cnt = ;
     while(scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3) != EOF)
     {
         int res = abs(x2 - x1) > abs(y2 - y1) ? abs(x2 - x1) : abs(y2 - y1);

         if((x3 >= x1 && x3 <= x2) || (x3 <= x1 && x3 >= x2))
         {
                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))

                       res++;
         }
         printf("Case %d: %d\n", ++cnt, res);
     }
 }

官方标程：

 // Rujia Liu
 #include<cstdio>
 #include<algorithm>
 #include<iostream>
 using namespace std;

 #define dist(a,b) (max(abs(r[a]-r[b]),abs(c[a]-c[b])))

 int main() {
   int r[], c[], kase = ;
   while(cin>>r[]>>c[]>>r[]>>c[]>>r[]>>c[]) {
     int dr = abs(r[]-r[]);
     int dc = abs(c[]-c[]);
     int d = max(dr, dc);
     if(dr == dc && dist(,) == dist(,) + dist(,)) d++;
     printf("Case %d: %d\n", ++kase, d);
   }
   return ;
 }