读书人
栏目▼

【C# 每天一题1】猫捉老鼠

发布时间： 2012-12-27 10:17:09 作者： rapoo

【C# 每日一题1】猫捉老鼠


[解决办法]
引用:
你可以认为老鼠每次行动都在猫之前


那么，猫在哪个时间点呢做决定是走还是跳？老鼠移动前还是移动后？
[解决办法]
感觉上用2进制方便点
[解决办法]

int dest,beginmouse,begincat;

struct _node
{
int catpos;
int mousepos;
};

_node queue[10000000];
int head,tail;

int step;
int minstep;

void Run()
{
int casenum;
scanf("%d",&casenum);
while(casenum--)
{
scanf("%d %d %d",&dest,&begincat,&beginmouse);
head = tail = 0;
step = -1;
minstep = -1;
if(begincat >= beginmouse)
{
if((begincat-beginmouse)%2 == 0)step = (begincat-beginmouse)/2;
}
else
{
queue[0].catpos = begincat;
queue[0].mousepos = beginmouse;
head = 0;tail = 1;
}
while(head < tail)
{
if(queue[head].mousepos-queue[0].mousepos >= minstep && minstep != -1)
{
head++;
continue;
}
//分三种情况
//1 猫后退一步
queue[tail].mousepos = queue[head].mousepos+1;
queue[tail].catpos = queue[head].catpos-1;
if(queue[tail].mousepos != dest)tail++;

//2 猫前进一步
queue[tail].mousepos = queue[head].mousepos+1;
queue[tail].catpos = queue[head].catpos+1;
if(queue[tail].mousepos != dest)tail++;

//猫前跳一步
int curmouse = queue[tail].mousepos = queue[head].mousepos+1;
int curcat = queue[tail].catpos = queue[head].catpos*2;
if(curcat >= curmouse)
{
if((curcat-curmouse)%2 == 0 && queue[tail].mousepos+(curcat-curmouse)/2 <= dest)
{
//printf("%d %d\n",queue[tail].mousepos,queue[tail].catpos);
step = queue[tail].mousepos-queue[0].mousepos+(curcat-curmouse)/2;
if(step < minstep 
[解决办法]
 minstep == -1)minstep = step;
}
}
else tail++;
head++;
}
printf("%d\n",minstep);
}
}


int main()
{
Run();
while(1);
return 0;
}

[解决办法]
时间有限只写了 
猫>鼠>家这种情况的
鼠>猫>家
猫>家>鼠
家>鼠>猫
家>猫>鼠
鼠>家>猫 都差不多

winForm 做的小动画

        private void MSGame() 
 
        {
            int cat = int.Parse(textBox2.Text);
            int mouse = int.Parse(textBox3.Text);
            int home = int.Parse(textBox1.Text);

            int mtoh=0;

            this.lblS.Location = new System.Drawing.Point(10+mouse, 75);
            this.lblJ.Location = new System.Drawing.Point(10+home, 75);
            this.lblM.Location = new System.Drawing.Point(10+cat, 75);


            if (mouse == home)
            { textBox4.Text = "猫抓到老鼠!"; }
            else if (mouse < home)
            {
                mtoh = home - mouse;
                for (int i = 0; i <= mtoh; i++)
                {
                    this.lblS.Location = new System.Drawing.Point(10 + mouse + i, 75);
                    Application.DoEvents();
                    if ((cat * 2) <= (mouse + i))
                    {
                        cat = cat * 2;
                    }
                    else if ((cat * 2) > (mouse + i) && ((cat * 2) - (mouse + i)) < cat)
                    {
                        cat = cat * 2;
                    }
                    else
                    {
                        cat--;
                    } 
 
                    this.lblM.Location = new System.Drawing.Point(10 + cat, 75);
                    Application.DoEvents();

                    if ((mouse + i) == cat && i != mtoh)
                    { textBox4.Text = String.Format("猫用{0}步,抓到老鼠!", i); break; }
                    else
                    { textBox4.Text = "猫抓到老鼠!"; }
                    System.Threading.Thread.Sleep(100);
                }
            }

            
        }


[解决办法]
按照acm的标准写了一个，去掉Readkey差不多可以直接用

using System;

namespace CSharpTest
{
    class Program
    {
        public static int[,] Matrix;
        public static int Max;
        public static int MaxStep = 10000;

        public static void Main()
        {
            Max = 100;
            Matrix = new int[Max + 1, Max + 1];
            int testCount = int.Parse(Console.ReadLine());
            Matrix[1, 2] = 2;

            for (int i = 0; i < testCount; i++)
            {
                int home = int.Parse(Console.ReadLine());
                string[] nums = Console.ReadLine().Split(' ');

                int cat = int.Parse(nums[0]);
                int mouse = int.Parse(nums[1]);

                int step = 0;

                if (home >= mouse)
                    step = Serach(mouse, cat, 1); 
 
                else
                    step = Serach(mouse, cat, -1);

                if (step >= Math.Abs(home - mouse))
                    Console.WriteLine(-1);
                else
                    Console.WriteLine(step);
            }

            Console.ReadKey();
        }

        public static int Serach(int i, int j, int k)
        {
            if (i == j)
                return 0;

            if (i < 0 
[解决办法]
 i > Max 
[解决办法]
 j < 0 
[解决办法]
 j > Max)
                return MaxStep;

            if (Matrix[i, j] == 0)
            {
                if (j > i)
                {
                    if (((j - i) & 1) == 0)
                        Matrix[i, j] = (j - i) >> 1;
                    else
                        Matrix[i, j] = Serach(i + k, j - 1, k) + 1;
                }
                else
                {
                    Matrix[i, j] = MaxStep;
                    Matrix[i, j] = Math.Min(Matrix[i, j], Serach(i + k, j * 2, k)); 
 
                    Matrix[i, j] = Math.Min(Matrix[i, j], Serach(i + k, j + 1, k));
                    Matrix[i, j] = Math.Min(Matrix[i, j], Serach(i + k, j - 1, k));
                    Matrix[i, j]++;
                }
            }

            return Matrix[i, j];
        }
    }
}

[解决办法]
引用:
按照acm的标准写了一个，去掉Readkey差不多可以直接用

C# code
using System;

namespace CSharpTest
{
    class Program
    {
        public static int[,] Matrix;
        public static int Max;
        public static int ……


litaoye v5
[解决办法]
#include "stdio.h"
int dest,beginmouse,begincat;

struct _node
{
    int catpos;
    int mousepos;
};

_node queue[10000000];
int head,tail;

int step;
int minstep;

void Run()
{
    int casenum;
    scanf("%d",&casenum);
    while(casenum--)
    {
        scanf("%d %d %d",&dest,&begincat,&beginmouse);
        head = tail = 0;
        step = -1;
        minstep = -1;
        if(begincat >= beginmouse)
        {
                if((begincat-beginmouse)%2 == 0)step = (begincat-beginmouse)/2;
        }
        else
        {
            queue[0].catpos = begincat;
            queue[0].mousepos = beginmouse;
            head = 0;tail = 1;
        }
        while(head < tail)
        {
            if(queue[head].mousepos-queue[0].mousepos >= minstep && minstep != -1)
            {
                head++; 
 
                continue;
            }
            //分三种情况
            //1 猫后退一步
            queue[tail].mousepos = queue[head].mousepos+1;
            queue[tail].catpos = queue[head].catpos-1;
            if(queue[tail].mousepos != dest)tail++;

            //2 猫前进一步
            queue[tail].mousepos = queue[head].mousepos+1;
            queue[tail].catpos = queue[head].catpos+1;
            if(queue[tail].mousepos != dest)tail++;

            //猫前跳一步
            int curmouse = queue[tail].mousepos = queue[head].mousepos+1;
            int curcat = queue[tail].catpos = queue[head].catpos*2;
            if(curcat >= curmouse)
            {
                if((curcat-curmouse)%2 == 0 && queue[tail].mousepos+(curcat-curmouse)/2 <= dest)
                {
                //    printf("%d %d\n",queue[tail].mousepos,queue[tail].catpos);
                    step = queue[tail].mousepos-queue[0].mousepos+(curcat-curmouse)/2;
                    if(step < minstep 
[解决办法]
 minstep == -1)minstep = step;
                }
            }
            else tail++;
            head++;
        }
        printf("%d\n",minstep);
    }
}


int main()
{
    Run();
    return 0;
}


[解决办法]
                该回复于2011-10-25 12:35:41被版主删除            
[解决办法]
思路比较简单，只说老鼠一直往100跑的情况吧，设f(i,j)表示老鼠在i，猫在j，猫追上老鼠所需的最少步骤

当j > i(也就是双方对着走的时候)，如果(j - i) mod 2 = 0，那么经过(j - i) / 2步可以追上
 
 
当j > i, (j - i) mod 2 == 1时，猫肯定还是朝老鼠的方向走（除了1,2为特例），经过1步之后，老鼠位置为i+1，猫的位置为j-1，因此问题转化为f(i+1,j-1)，所以这种情况下f(i,j) = f(i+1,j-1) + 1

当j < i时，猫的情况比较复杂，有3种行动方式，因此对应3种情况，

f(i,j) = f(i+1,j-1) + 1 向着0走
f(i,j) = f(i+1,j+1) + 1 向着100走
f(i,j) = f(i+1,j*1) + 1 跳着走

不过我们只需要选择步数最少的方案，因此

f(i,j) = Min(f(i+1,j-1),f(i+1,j+1),f(i+1,j*1)) + 1

剩下的就是开一个i * j的数组，把曾经算出过的结果记录下来就可以。

引用:
妄能解释一下您的代码和思路

[解决办法]

        static void Main()
        {
            int tom = 20;
            int jerry = 88;
            int home = 100;
            int r = -1;
            for (int n = 1; n <= home - jerry; n++)
            {
                if (fn1(n, jerry + n, tom))
                {
                    r = n;
                    break;
                }
            }
            Console.WriteLine(r);
            Console.Read();
        }
        //在n次迭代内, x可否通过规定变换成为y
        static bool fn1(int n,int x, int y)
        {                       
           
            if (n <= 0) return x==y;
            int d = Math.Abs(x - y);
            if (d <= n && (d & 1) == (n & 1)) return true;
            bool r = fn1(n-1,x-1,y) 
[解决办法]
 fn1(n-1,x+1,y);
            if((x & 1) ==0) r = r 
[解决办法]
 fn1(n-1,x/2,y);             
 
            return r;
        }

[解决办法]
表示对这类东西比较感兴趣
[解决办法]
引用:
时间有限只写了 
猫>鼠>家这种情况的
鼠>猫>家
猫>家>鼠
家>鼠>猫
家>猫>鼠
鼠>家>猫 都差不多

winForm 做的小动画
C# code

        private void MSGame()
        {
            int cat = int.Parse(textBox2.Text);
            int mouse ……


结合 Silverlight 实现是不是更生动
读书人网 >C#

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net