1. ACM训练题汇集

   1 
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 
   6 #define TPS 4
   7 
   8 #define STEP                  \
   9  do {                         \
  10    tt =1;                     \
  11    for(; d<TPS; d++)            \
  12    {                          \
  13        tr=r+tp[d][0], tc=c+tp[d][1];         \
  14        if (tr>=0 && tr <n && tc>=0 && tc <m && p[tr][tc]=='.')    \
  15          {  r = tr, c = tc;   \
  16             p[r][c] = '0'+d;    \
  17             st[t] = d;        \
  18             t++, s++;         \
  19             tt  = 0;           \   
  20             break;             \
  21          }                     \                
  22    }                           \
  23 } while(0)
  24      
  25      
  26 #define  OMAX  25
  27 
  28 void printp(int n, int m, char **p)
  29 {
  30   int i, j;
  31   fprintf(stdout, "\n");
  32   for(i=0; i<n; i++)
  33   {
  34     for(j=0; j<m; j++)
  35       fprintf(stdout, "%c", p[i][j]);
  36     fprintf(stdout, "\n");
  37   }
  38 }
  39 
  40 int count(int n, int m, char **p)
  41 {
  42   int st[OMAX*OMAX];
  43   int s, d;
  44   int tt;
  45   signed int t;
  46   signed int r, c, tr, tc;
  47   int tp[TPS][2] = { {+1, 0}, {-1, 0}, {0, +1}, {0, -1} };
  48   //printp(n,m,p);
  49   for(r=0; r<n; r++)
  50     {
  51       for(c=0; c<m; c++)
  52         if(p[r][c]=='@')
  53           break;
  54       if(p[r][c]=='@')
  55         break;
  56     }
  57   for(s=1, st[0]=TPS, t=1; t>0;)
  58     {
  59       d=0;
  60       STEP;
  61       //fprintf(stderr, "(%d, %d)\t", r, c);
  62       //printp(n,m,p);
  63 
  64       while (t>0 && tt == 1) 
  65         {
  66           t--;
  67           d = st[t];
  68           r -= tp[d][0];
  69           c -= tp[d][1];
  70           d++;
  71           STEP;
  72           //fprintf(stderr, "(%d, %d)\t", r, c);
  73         }
  74     }
  75   return s;
  76 }
  77 
  78 int pp(char **p)
  79 {
  80   int n, m;
  81   int i;
  82   fscanf(stdin, "%d%d", &m, &n);
  83   for(i=0; i<n ;i++)
  84     fscanf(stdin,"%s", p[i]);
  85 
  86   if(n==0 || m==0)
  87     return 0;
  88   else
  89     return count(n, m, p);
  90 }
  91 
  92 int main()
  93 {
  94   int i;
  95   char **p;
  96   p = (char **)malloc(sizeof(char*)*OMAX);
  97   for(i=0; i< OMAX; i++)
  98     p[i]=(char *)malloc(sizeof(char)*OMAX);
  99   do
 100     {
 101       i=pp(p);
 102       if(i!=0)
 103         fprintf(stdout, "%d\n", i);
 104     }
 105   while(i!=0);
 106 
 107   return 0;
 108 }
 109 

   1 
   2 #include<stdio.h>
   3 #include<string.h>
   4 typedef struct 
   5 {  char ch[50];
   6    int len;
   7 }SqString;
   8 int creat_string(SqString s1,SqString s2,SqString s);
   9 int check(int a[50][50]);
  10 
  11 
  12 void main()
  13 {  int i=0;
  14    SqString s,s1,s2;
  15    scanf("%s",&s1.ch);
  16    s1.len=strlen(s1.ch); 
  17    scanf("%s",&s2.ch);
  18    s2.len=strlen(s2.ch);
  19    for(i=0;i<10;i++){
  20 
  21    s.ch[i]='*';
  22         s.len++;
  23    }
  24    creat_string(s1,s2,s);
  25    return ;
  26 }
  27 int creat_string(SqString s1,SqString s2,SqString &s)
  28 {  int i,j,k,m,n,t=0;
  29    int a[50][50];
  30    int b[50][50];
  31    for(i=0;i<50;i++)
  32            for(j=0;j<50;j++)
  33            a[i][j]=b[i][j]=0;
  34    for(i=0;i<s1.len;i++)
  35            for(j=0;j<s2.len;j++)
  36                    if(s1.ch[i]==s2.ch[j])
  37                            a[i][j]=1;
  38    k=1;
  39    while(check(a))
  40    {
  41           for(i=0;i<s1.len;i++)
  42         for(j=0;j<s2.len;j++)
  43                 {
  44                b[i][j]=a[i][j];
  45                 }
  46           for(m=0;m<s1.len;m++)
  47           {   while(i<s1.len&&j<s2.len)
  48           {     if(a[i][j]==1&&a[i+k][j+k]==0)
  49           {         a[i][j]=0;
  50                     i=i+k+1;
  51                                 j=j+k+1;
  52           }
  53                 else
  54                         {i++;
  55                          j++;
  56                         }
  57           }
  58           }
  59           for(n=0;n<s2.len;n++)
  60           {   while(i<s1.len&&j<s2.len)
  61           {     if(a[i][j]==1&&a[i+k][j+k]==0)
  62           {         a[i][j]=0;
  63                     i=i+k+1;
  64                                 j=j+k+1;
  65           }
  66                 else
  67                         {i++;
  68                          j++;
  69                         }
  70           }
  71           }
  72           k++;
  73         }
  74         while(i<s1.len&&j<s2.len)
  75                         if(b[i][j]==1)
  76                                 for(;t<k;t++)
  77                                 { s.ch[t]=s1.ch[i];
  78                                   i++;
  79                                 }
  80         printf("%s",s.ch);
  81         return 1;
  82 }
  83 int check(int a[50][50])
  84 { int i,j;
  85   for(i=0;i<50;i++)
  86         for(j=0;j<50;j++)
  87                         if(a[i][j]!=0)
  88                                 return 1;
  89   return 0;
  90 }
  91 
  92 ...