Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Fukashigi
{
    internal class Program
    {
        static int width = 5;  // n+1を設定
        static int height = 5;  // m+1を設定
        static int goal = width * height - 1;
        static int count = 0;

        static void MoveNext(Stack<int> stack, int x)
        {
            if (stack.Contains(x))
            {
                return;
            }
            stack.Push(x);
            if (x == goal)
            {
                count++;
                Console.Write($"{count}: ");
                var list = stack.ToArray().Reverse();
                foreach(var i in list)
                { 
                    Console.Write($" {i}");
                }
                Console.WriteLine();
                stack.Pop();
                return;
            }
            int next = -1;
            // 上にいけるか
            if (x >= width)
            {
                next = x - width;
                MoveNext(stack, next);
            }
            // 下に行けるか
            if (x <= goal - width)
            {
                next = x + width;
                MoveNext(stack, next);
            }
            // 右に行けるか
            if (x % width < width - 1)
            {
                next = x + 1;
                MoveNext(stack, next);
            }
            // 左に行けるか
            if (x % width > 0)
            {
                next = x - 1;
                MoveNext(stack, next);
            }
            stack.Pop();
        }
        static void Main(string[] args)
        {
            Stack<int> stack = new Stack<int>();
            MoveNext(stack, 0);
            Console.WriteLine($"{count} paths");
        }
    }
}