7*12的矩形,14个单词.
枚举每个单词,从格子的每个点的八个方向进行判断,
复杂度O(7*12*14*8*len),还是很快的说.只不过有些细节注意一下就是了.
len为单词的长度.
汗,都懒得写代码了.......... cheat了一个威望，哈．．．．．
终于从导员那儿求到提示了。。
但还是不明白。。@.@
希望各位高手哥哥可以看得明吧。。 拜托拉。。
-----------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
/****************************************************************/
/* Constants and structure definitions */
/* Constant for the maximum size of all arrays */
#define MAXSIZE 50
/* Structure to hold information about the rectangular grid */
typedef struct
{
/* The letters in the grid */
char letters[MAXSIZE][MAXSIZE];
/* The number of rows in the grid */
int nRows;
/* The number of columns in the grid */
int nCols;
} GRID;
/* Structure to hold information about a search position */
typedef struct
{
/* The row number, starting from 0 */
int row;
/* The column number, starting from 0 */
int col;
} LOCATION;
/* Structure to hold information about the amount to move in a single
step of the searching process */
typedef struct
{
/* The amount to move in the row-direction: either -1, 0, or 1
depending on the direction of the search */
int deltaRow;
/* The amount to move in the column-direction: either -1, 0,
or 1 depending on the direction of the search */
int deltaColumn;
} MOVEMENT;
/* Enumeration for the possible search directions */
typedef enum {UP, DIAGUPRIGHT, RIGHT, DIAGDOWNRIGHT,
DOWN, DIAGDOWNLEFT, LEFT, DIAGUPLEFT} DIRECTION;
/****************************************************************/
/* Global variable definitions */
/* You should not need to add to this list */
/* A global variable for the rectangular grid of letters */
GRID grid;
/****************************************************************/
/* Functions */
/*
isValidGridEntry(c) returns true iff c is a valid character that can
appear in a grid-file.
*/
static bool isValidGridEntry(char c)
{
}
/*
isValidChar(c) returns true iff c is a valid character that can appear
in a words-file.
*/
static bool isValidChar(char c)
{
}
/*
trimLine(line) removes any trailing new-line or carriage-return
characters from the end of line.
*/
static void trimLine(char line[])
{
}
/*
readGrid(filename) reads the contents of the file named filename as a
grid-file, "filling" the grid global variable with information read
from the file. The function terminates the program if the file is
not a valid grid-file or if the corresponding grid would be too large
to store in the grid global variable.
*/
static void readGrid(char filename[])
{
}
/*
displayGrid(void) displays the rectangular grid of characters held
in the grid global variable.
*/
static void displayGrid(void)
{
}
/*
move(dir) returns a MOVEMENT structure that indicates how much to vary
an iteration through the rows and columns of the grid for a single
step of the searching process, when searching in a dir direction.
e.g. move(UP)={-1,0}; move(RIGHT)={0,1}; move(DIAGUPLEFT)={-1,-1}
*/
static MOVEMENT move(DIRECTION dir)
{
}
/*
isMatch(c, gridLetter) returns true iff c matches the (potentially
highlighted) gridLetter.
*/
static bool isMatch(char c, char gridLetter)
{
}
/*
searchForm(word, loc, dir) returns true iff word appears in the grid
starting at position loc in the dir direction.
*/
static bool searchFrom(char word[], LOCATION loc, DIRECTION dir)
{
}
/*
highlightLetter(c) returns the highlighted version of c.
*/
static char highlightLetter(char c)
{
}
/*
foundWord(word, loc, dir) highlights word in the grid. This function
assumes word has already been found in the grid starting at position
loc in the dir direction.
*/
static void foundWord(char word[], LOCATION loc, DIRECTION dir)
{
}
/*
search(word) returns the the number of times word appears in the grid.
*/
static int search(char word[])
{
}
/*
processWords(filename) reads the contents of the file named filename
as a words-file, searching for each word in turn in the grid. The
function terminates the program if the file is not a valid words-file.
The function also reports whether each word the file found in the
grid and the total number of words from the file found in the grid.
*/
static void processWords(char filename[])
{
}
/****************************************************************/
/* The main program */
int main(int argc, char *argv[])
{
/* Exit with an error if the the number of arguments (including
the name of the executable) is not 3 */
if(argc != 3)
{
fprintf(stderr, "Usage: %s grid-file words-file\n", argv[0]);
exit(EXIT_FAILURE);
}
else
{
/* Read the grid from file */
readGrid(argv[1]);
printf("Read grid from '%s'.", argv[1]);
printf(" The initial grid is:\n");
/* Display the contents of the grid */
displayGrid();
printf("\nProcessing words from file '%s'.\n", argv[2]);
/* Search for words, highlighting matches in the grid */
processWords(argv[2]);
printf("\nFinished task.");
printf(" The final grid is:\n");
/* Redisplay the contents of the grid */
displayGrid();
/* Finished successfully! */
exit(EXIT_SUCCESS);
}
return 0;
}
