hdu 2782 The Worm Turns

题目大意：

　　在地球上的一块长方形区域上，一个名叫Winston的毛毛虫从睡梦中醒来。这个长方形区域被分成很多小格子，并且每个格子上要么存在着食物，要么存在着是石头。这只虫虫漫无目的的徘徊着直到他感到有点饿了；这时它马上吃掉了在它这个格子里头的食物，然后选择了四个方向（北，南，东，西）中的一个方向移动，只要它能看到它前面的格子中有食物，它就会沿着这个方向一直爬。如果它看到它前面是石头，或者看到前面格子里头的食物它已经吃过了，或者前面是边界，它就向左边或者右边转弯。它永远不走重复地方。最终它到达一个足够远的地方它就会停下来打个嗝，午睡一会。

　　如下图1所示，'X'表示石头，其他位置表示食物。在这个例子里头，虫虫非常聪明的选择了它走的道路：它吃了每个格子里的食物。你的目标是帮助虫虫决定他应该从哪里开始才能吃到尽可能多的食物。

输入：会有许多测试用例输入。每一个测试以两个正数m和n开始，分别代表这个矩形区域的行和列的数目。行列的编号从0开始。接下来输入一个正整数r，表示有r个石头。接着一列2个整数的列表，表示石头的行和列。最后一个测试用例后面跟着2个0。m*n的值不会超过625。

输出：每个例子打印测试用例的编号，然后跟着四个值：食物的数量行列方向。食物的数量是Winston能吃到的食物数量最大值，（行，列）是winston吃到食物数量的起始位置，方向是E、N、S、W其中的一个，表面最初的方向。如果不止一个开始位置，那么选择字典序最小行列。如果起始位置有不同的方向，按照E，N，S，W的顺序选择第一个。假设总是至少有一块食物靠近虫虫的初始位置。

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 const int N = 630;
  6 const int d[4][2] = { {0,1}, {-1,0}, {1,0}, {0,-1} };//方向：向右，向上，向下，向左
  7 int board[N][N];  //棋盘
  8 bool visit[N][N]; //标记数组
  9 int m, n;         //行、列
 10 int startDir, startRow, startCol;      //记录出发点信息
 11 int resDir, resRow, resCol, maxFoodNum;//记录结果
 12 
 13 /* 初始化函数 */
 14 void init(void)
 15 {
 16     maxFoodNum = -1;
 17     memset(visit, 0, sizeof(visit));
 18     for (int i = 0; i < m; ++i)
 19         for (int j = 0; j < n; ++j)
 20             board[i][j] = 0;
 21 }
 22 
 23 /* 判断是否越界 */
 24 inline bool inBoard(int row, int col)
 25 {
 26     return 0 <= row && row < m && 0 <= col && col < n;
 27 }
 28 
 29 /* dfs搜索 */
 30 void dfs(int row, int col, int food)
 31 {
 32     for (int i = 0; i < 4; ++i)
 33     {
 34         if (1 == food) //food等于1的地方，就是搜索开始的地方，需要记录下开始时的一些信息
 35         {
 36             startDir = i;
 37             startRow = row;
 38             startCol = col;
 39         }
 40         int nextRow = row + d[i][0];//向前试探一步
 41         int nextCol = col + d[i][1];
 42 
 43         //如果这一步没有越界，之前没有访问过，而且这地方有食物，说明这个方向可以走。否则换一个方向走
 44         if (true == inBoard(nextRow, nextCol) && false == visit[nextRow][nextCol] && 0 == board[nextRow][nextCol])
 45         {
 46             do
 47             {
 48                 visit[nextRow][nextCol] = true;
 49                 food += 1;
 50                 nextRow += d[i][0];
 51                 nextCol += d[i][1];
 52             }while (true == inBoard(nextRow, nextCol) && false == visit[nextRow][nextCol] && 0 == board[nextRow][nextCol]);
 53 
 54             //试探的这一步要么越界了，要么之前访问过，要么这一步走到石头上了，说明这一步走到头了。先退一步回去，然后转弯。
 55             nextRow -= d[i][0];
 56             nextCol -= d[i][1];
 57 
 58             dfs(nextRow, nextCol, food);   //拐弯
 59 
 60             while (!(nextRow == row && nextCol == col)) //回溯,worm返回到(row, col)点上，并且状态也返回到之前的状态
 61             {
 62                 visit[nextRow][nextCol] = false;
 63                 food -= 1;
 64                 nextRow -= d[i][0];
 65                 nextCol -= d[i][1];
 66             }
 67         }
 68     }
 69 
 70     //无路可走了，需要回去了。回去之前先判断是否吃到了比之前多的食物，如果是，则记录信息。
 71     if (maxFoodNum < food)
 72     {
 73         resRow = startRow;
 74         resCol = startCol;
 75         resDir = startDir;
 76         maxFoodNum = food;
 77     }
 78 }
 79 
 80 /* 搜索函数：从(r,c)开始搜索 */
 81 void dfsTravel(void)
 82 {
 83     for (int i = 0; i < m; ++i)
 84         for (int j = 0; j < n; ++j)
 85             if (0 == board[i][j])  //(i,j)有食物才能从这里搜索
 86             {
 87                 visit[i][j] = true;
 88                 dfs(i,j,1);
 89                 visit[i][j] = false;
 90             }
 91 }
 92 
 93 /* 输出结果 */
 94 void outputResult(int caseCount)
 95 {
 96     printf("Case %d: %d %d %d ", caseCount, maxFoodNum, resRow, resCol);
 97     switch (resDir)
 98     {
 99     case 0: printf("E
"); break;
100     case 1: printf("N
"); break;
101     case 2: printf("S
"); break;
102     case 3: printf("W
"); break;
103     }
104 }
105 
106 int main(void)
107 {
108     int caseCount = 1;     //记录当前case编号
109     int stoneCount;        //石头的数量
110     int row, col;
111     while (scanf("%d %d", &m, &n), m || n)
112     {
113         init();
114         scanf("%d", &stoneCount);
115         for (int i = 0; i < stoneCount; ++i)
116         {
117             scanf("%d %d", &row, &col);
118             board[row][col] = 1; //1代表石头,0代表食物
119         }
120         dfsTravel();
121         outputResult(caseCount);
122         ++caseCount;
123     }
124     return 0;
125 }