tc1

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

#define MAX_H 15
#define MAX_W 8


#define WALL 1
#define PASS 2
#define GOAL 3

int T;
int W;
int H;
int Answer;

int Map[MAX_H + 4][MAX_W + 4];
int CountMap[MAX_H + 4][MAX_W + 4];

enum{
    NONE,
    UP,
    DOWN,
    LEFT,
    RIGHT
};

int Search(int w, int h, int depth, int dir)
{

    if (Map[h][w] == WALL) return 0;

    if (CountMap[h][w] > depth) return 0;

    if (Map[h][w] == GOAL){
        if (Answer < depth)  {
            Answer = depth;
        }
        return 1;
    }

    Map[h][w] = PASS;

    int old = CountMap[h][w];

    int ret = 0;

    CountMap[h][w] = depth;


    if (Map[h - 1][w - 1] != PASS && Map[h][w - 1] != PASS && Map[h + 1][w - 1] != PASS) {
        if (Search(w - 1, h, depth + 1, LEFT))    ret = 1;
    }
    if (Map[h - 1][w + 1] != PASS && Map[h][w + 1] != PASS && Map[h + 1][w + 1] != PASS) {
        if (Search(w + 1, h, depth + 1, RIGHT)) ret = 1;
    }
    if (Map[h - 1][w - 1] != PASS && Map[h - 1][w] != PASS && Map[h - 1][w + 1] != PASS) {
        if (Search(w, h - 1, depth + 1, UP)) ret = 1;
    }
    if (Map[h + 1][w - 1] != PASS && Map[h + 1][w] != PASS && Map[h + 1][w + 1] != PASS) {
        if (Search(w, h + 1, depth + 1, DOWN)) ret = 1;
    }

    Map[h][w] = NONE;

    if (ret == 0) CountMap[h][w] = old;
    return ret;

}

int main()
{
    freopen("input(1).txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d", &T);

    int testcase;
    int h, w;

    for (testcase = 1; testcase <= T; testcase++)
    {
        memset(Map, 0, (MAX_H + 4)*(MAX_W + 4) * 4);
        memset(CountMap, 0, (MAX_H + 4)*(MAX_W + 4) * 4);

        Answer = 0;
        scanf("%d %d", &W, &H);

        for (h = 2; h <= H + 1; h++){
            for (w = 2; w <= W + 1; w++){
                scanf("%d", &Map[h][w]);
            }
            Map[h][0] = PASS;
            Map[h][W + 3] = PASS;
        }

        Map[1][0] = PASS;
        Map[1][W + 3] = PASS;

        for (w = 0; w <= W + 3; w++){
            Map[0][w] = PASS;
        }

        Map[H + 2][0] = PASS;
        Map[H + 2][W + 3] = PASS;

        for (w = 0; w <= W + 3; w++){
            Map[H + 3][w] = PASS;
        }
        Map[H + 1][W + 1] = GOAL;

        Search(2, 2, 1, NONE);


        printf("#%d %d\n", testcase, Answer);


    }


}