fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>
  4.  
  5. struct point{//結構存x,y座標，和指向下個座標 
  6.         int x;
  7.         int y;
  8.         struct point *next;
  9.         };
  10.  
  11. typedef  struct point POINT;//讓節點好假設       
  12.  
  13. int MAX(int Mx[],int My[],int MummyNum){ //求所有木乃伊X，Y座標的最大值 
  14.     int i,j,max1,max2;//設定變數，先求X絕對值的最大，在求Y，然後比較 
  15.     max1=abs(Mx[0]);//X最大，設第一個最大 
  16.     max2=abs(My[0]);//Y最大，設第一個最大  
  17.     for(i=1;i<MummyNum;i++){//把每個點都下去比較，分別求出X及Y部分的最大 
  18.         if(abs(Mx[i])>=max1){max1=abs(Mx[i]);}                    
  19.         if(abs(My[i])>=max2){max2=abs(My[i]);}
  20.                                              }
  21.     if(max1>=max2){return max1;}//比較X及Y部分的最大，回傳 
  22.     else 
  23.     return max2;
  24. }                                              
  25. void close(int x,int y,int Hx,int Hy,FILE *ptr1){//讓點x,y往目的地Hx,Hy移動，印到檔案ptr1 
  26.  if((Hx==x)&&(Hy==y)){
  27.        if(abs(Hx)>abs(Hy)){if(Hx>=0){x++;fprintf(ptr1,"(%d,%d)",x,y);}//判斷走到目的地時，判斷x,y座標大小，詳細看專題報告               
  28.                            if(Hx<0){x--;fprintf(ptr1,"(%d,%d)",x,y);}}
  29.        else
  30.        {                      
  31.           if(Hy>=0){y++;fprintf(ptr1,"(%d,%d)",x,y);}               
  32.           if(Hy<0){y--;fprintf(ptr1,"(%d,%d)",x,y);}            
  33.  
  34.                       }              
  35.                       }    
  36.  else if((Hx>x)&&(Hy==y)){x++;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的右方，所以往右走一步，再把點帶入，重複執行 
  37.  else if((Hx>x)&&(Hy>y)){x++;y++;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的右上方，所以往右上走一步，再把點帶入，重複執行
  38.  else if((Hx==x)&&(Hy>y)){y++;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的上方，所以往上走一步，再把點帶入，重複執行                         
  39.  else if((Hx<x)&&(Hy>y)){x--;y++;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的左上方，所以往左上走一步，再把點帶入，重複執行
  40.  else if((Hx<x)&&(Hy==y)){x--;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的左方，所以往左走一步，再把點帶入，重複執行                                
  41.  else if((Hx<x)&&(Hy<y)){x--;y--;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的左下方，所以往左下走一步，再把點帶入，重複執行
  42.  else if((Hx==x)&&(Hy<y)){y--;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的下方，所以往下走一步，再把點帶入，重複執行
  43.  else if((Hx>x)&&(Hy<y)){x++;y--;fprintf(ptr1,"(%d,%d)",x,y);close(x,y,Hx,Hy,ptr1);}//目的地在點的右下方，所以往右下走一步，再把點帶入，重複執行
  44.  
  45.  
  46.                                                  }
  47.  
  48. int find(POINT *data,int a,int b){//尋找點，被儲存的座標鏈結裡，如果有此座標，回傳0，沒有就1 
  49.     while(data!=NULL){
  50.   if(data->x==a&&data->y==b){return 0;}   
  51.     else 
  52.     data=data->next;
  53. }
  54.    return 1; 
  55. }
  56.  
  57. int Mx[10000];//全域，存木乃伊座標和人座標 
  58. int My[10000];
  59. int Hx[10000];
  60. int Hy[10000];                                                 
  61. int main(){
  62.  
  63.     FILE *ptr,*ptr1;//開出2個指向檔案的指標 
  64.     int MummyNum;//木乃伊個數 
  65.     int result=0,tmp=0,max,check=1;//參數，功能會講解 
  66.     POINT *point,*current,*previous;//節點指標 
  67.     int s1,s2,s3,s4;//參數 
  68.  
  69.     int STEP=1,num=1;//參數，功能會講解 
  70.     int a,b,c,d,e,f,i,j,k,l,q=1;//一些小變數，其中q為次數，亦即總共執行幾次 
  71.  
  72.     ptr=fopen("input1.txt","r");//開檔，只能讀取 
  73.     ptr1=fopen("output1.txt","w");//開檔，只能寫入 
  74.     if(ptr!=NULL&&ptr1!=NULL){//如果以上2個開檔成功的話，就執行以下動作 
  75.  
  76.     fscanf(ptr,"%d",&MummyNum);//從讀取檔案讀進木乃伊個數 
  77.     while(MummyNum!=(-1)){//如果木乃伊個數不等於-1，執行以下動作 
  78.  
  79.     for(i=0;i<MummyNum;i++){//讀取木乃伊的座標                         
  80.  
  81.         fscanf(ptr,"%d%d",&Mx[i],&My[i]);                     
  82.                                    }
  83.     max=MAX(Mx,My,MummyNum);//求所有木乃伊X，Y座標的最大值，作用請看簡報 
  84.     STEP=1;//步數一開始為一步 
  85.  
  86.  
  87.            check=1;                      
  88.     while(check!=0){//要判斷以原點為中心向外擴張的面積是否有被木乃伊擴張的覆蓋，其中check一開始只是驅動while 
  89.           check=0;    //接下來的check將等於沒被覆蓋的面積，因為都被覆蓋，理論上等於0             
  90.  
  91.           free(point);//釋放節點資料 
  92.  
  93.  
  94.     for(i=0;i<MummyNum;i++){
  95.         a=Mx[i]+STEP;//把每個木乃伊所擴張的面積覆蓋，分為上下左右 
  96.         b=Mx[i]-STEP;
  97.         c=My[i]+STEP;
  98.         d=My[i]-STEP;
  99.  
  100.          if(i==0){
  101.        for(j=b;j<=a;j++){ //把所有被覆蓋面積的點座標，存成鏈結 
  102.           for(k=d;k<=c;k++){
  103.             current=(POINT *)malloc(sizeof(POINT));current->x=j;current->y=k;if(j==b&&k==d){point=current;previous=current;}else{previous->next=current;current->next=NULL;previous=current;}
  104.                      }} 
  105.                      }
  106.        else{
  107.          for(j=b;j<=a;j++){ 
  108.            for(k=d;k<=c;k++){
  109.             current=(POINT *)malloc(sizeof(POINT));current->x=j;current->y=k;previous->next=current;current->next=NULL;previous=current;}  
  110.             }}
  111.              }
  112.        e=(-1)*STEP;/*擴張人的範圍，判斷是否被覆蓋*/ 
  113.        f=STEP;
  114.        for(i=e;i<=f;i++){  /*判斷人所行範圍內，是否已全部被木乃伊覆蓋，用FIND尋找那個鏈結裡的點座標是否符合，沒找到會+1*/ 
  115.          for(j=e;j<=f;j++){
  116.              check+=find(point,i,j);                
  117.                       }}      
  118.         STEP++;/*步數一值增加*/                   
  119.  
  120.        if((STEP-1)>max){fprintf(ptr1,"case%d:NEVER!!",q);break;}//如果超過最大值，則抓不到，看專題報告 
  121.                     }           
  122.  
  123.  
  124.  
  125.  
  126.     if((STEP-1)<=max){//如果不是never，則代表會被抓到                           
  127.  
  128.  
  129.  
  130.  
  131.         tmp=STEP-2;//我們要找出前一步的情況，因為STEP往上加會多一步，所以-1為正確步數，在-1才是前ㄧ步 
  132.         free(point);//釋放節點資料
  133.         s1=0;//驅動變數 
  134.         s2=0;
  135.         s3=0;
  136.         s4=0;                   
  137.       for(i=0;i<MummyNum;i++){
  138.         a=Mx[i]+tmp;//把每個木乃伊所擴張的面積覆蓋，分為上下左右 
  139.         b=Mx[i]-tmp;
  140.         c=My[i]+tmp;
  141.         d=My[i]-tmp;
  142.  
  143.          if(i==0){//把前一步被覆蓋時的所有座標儲存成鏈結 
  144.        for(j=b;j<=a;j++){ 
  145.           for(k=d;k<=c;k++){
  146.             current=(POINT *)malloc(sizeof(POINT));current->x=j;current->y=k;if(j==b&&k==d){point=current;previous=current;}else{previous->next=current;current->next=NULL;previous=current;}
  147.                      }} 
  148.                      }
  149.        else{
  150.          for(j=b;j<=a;j++){ 
  151.            for(k=d;k<=c;k++){
  152.             current=(POINT *)malloc(sizeof(POINT));current->x=j;current->y=k;previous->next=current;current->next=NULL;previous=current;}  
  153.             }}
  154.              }                     
  155.  
  156.  
  157.  
  158.  
  159.      e=(-1)*(tmp);//這時我們要找出這ㄧ步，位置為空的地方 
  160.      f=tmp;
  161.      for(i=e;i<=f;i++){current=point;s1+=find(current,f,i);if(s1!=0){Hx[tmp]=f;Hy[tmp]=i;break;}} //如果其中有點為空的，把它存下來，雖然有可能有2個以上 
  162.      for(i=e;i<=f;i++){current=point;s2+=find(current,e,i);if(s2!=0){Hx[tmp]=e;Hy[tmp]=i;break;}}//不過只需要一個，因此被置換掉沒差 
  163.      for(i=e;i<=f;i++){current=point;s3+=find(current,i,f);if(s3!=0){Hx[tmp]=i;Hy[tmp]=f;break;}}
  164.      for(i=e;i<=f;i++){current=point;s4+=find(current,i,e);if(s4!=0){Hx[tmp]=i;Hy[tmp]=e;break;}}
  165.  
  166.  
  167.  
  168.  
  169.      //做完以上，已經弄完一個情況了    
  170.         fprintf(ptr1,"case%d:%d(0,0)",q,STEP-1);//印出步數                           
  171.         close(0,0,Hx[tmp],Hy[tmp],ptr1);}//把原點朝著我們剛剛找出為空的位置前進 
  172.         fprintf(ptr1,"\n");
  173.         q++;//次數+1                       
  174.  
  175.  
  176.  
  177.         fscanf(ptr,"%d",&MummyNum);//重複跑，如果為-1，往下跳                                        
  178.  
  179.               }
  180.  
  181.       fprintf(ptr1,"THANKS!!\n");//結束程式  
  182.  
  183.  
  184. }
  185.  
  186.  
  187. fclose(ptr);//關檔 
  188. fclose(ptr1);//關檔 
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.       return 0;                      
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.     }
  210.  
  211.  
  212.  
  213.  
Runtime error #stdin #stdout 0.01s 2008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hEj3E
language:
C (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!