文字列の八方向検索 in C DouKaku?

文字列の八方向検索

与えられた矩形状の文字列中に存在する文字列"ウオリ"の位置を全て出力するプログラムを
書いてください。
文字列の検索方向は八方全てで、また連続している（左右や上下の境界をまたがない）ものを
対象とします。出力は起点"ウ"の座標と方向のリストにしてください。

サンプル入力：

リオウウリウ
ウオリウオリ
オリリオリウ
リリオオウオ

サンプル出力：

(2, 0), 左
(0, 1), 右
(0, 1), 下
(3, 1), 右
(4, 3), 左上

--
より一般には、任意の検索文字列への対応も考えてみてください。

post comment

Posted feedbacks - C

全角じゃないです。
#4624 を参考にして総当たりかつ上方向への検索としてみました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *lines[] = { "CBAACA",
                  "ABCABC",
                  "BCCBCA",
                  "CCBBAB",
                  NULL };

char *strrev( char *str ){
   char *h, *t, tmp;
   if( !str ) return NULL;
   h = t = str;
   while( *t++ ); t-=2;
   while( h < t ){
      tmp = *h;
      *h++ = *t;
      *t-- = tmp;
   }
   return str;
}

int search8way( char *target, char **lines ){
   char *buf, *revstr;
   int i,j,m,n;
   int len = strlen(target);
   buf = (char *)malloc( sizeof(char) * strlen(target) + 1 );
   revstr = (char *)malloc( sizeof(char) * strlen(target) + 1 );
   if( !target || !revstr ){
      free(target);
      free(revstr);
      return EXIT_FAILURE;
   }
   memset( buf, '\0', len );
   strrev( strncpy(revstr, target, len) );
   for( i = 0; lines[i]; i++ ){
      for( j = 0; lines[i][j]; j++ ){

         !strncmp( &lines[i][j], target, len ) && printf("(%d, %d), right\n", j, i);
         !strncmp( &lines[i][j], revstr, len ) && printf("(%d, %d), left\n", j+len-1, i);

         if( i < len - 1 ) continue;

         for( m = n = 0; m < len; m++, n++ ) buf[n] = lines[i-m][j];
         !strncmp( buf, target, len ) && printf("(%d, %d), up\n", j, i);
         !strncmp( buf, revstr, len ) && printf("(%d, %d), down\n", j, i-len+1);

         for( m = n = 0; m < len; m++, n++ ) buf[n] = lines[i-m][j+m];
         !strncmp( buf, target, len ) && printf("(%d, %d), right up\n", j, i);
         !strncmp( buf, revstr, len ) && printf("(%d, %d), left down\n", j+len-1, i-len+1);

         if( j < len - 1 ) continue;

         for( m = n = 0; m < len; m++, n++ ) buf[n] = lines[i-m][j-m];
         !strncmp( buf, target, len ) && printf("(%d, %d), left up\n", j, i);
         !strncmp( buf, revstr, len ) && printf("(%d, %d), right down\n", j+len-1, i-len+1);

      }
   }
   free(target);
   free(revstr);
   return EXIT_SUCCESS;
}

int main( void ){
   return search8way("ABC", lines);
}

DouKaku?

文字列の八方向検索

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq