【C# 每日一题1】猫捉老鼠
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);
}
}
}
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];
}
}
}
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;
}
