2014
02-10

# Manipulating the Power Square

Rosalina finds Super Mario puzzling over the Power Square and gives him another hint on how to unlock its power. ”Keep swapping 0 with one of its neighbors! I’ll tell you which neighbor,” Rosalina says to Mario. Rosalina then gives Mario a sequence of directions on which neighbor to swap with 0.

Input is a description of of the Power Square, followed by a number of commands. The first line is the size of the Power Square n. You may assume n<=100. The second line contains the n2 values in the Power Square, separated by spaces. Values start from the top left corner and move from left to right, moving down one row to the leftmost position when a row is filled.
Following the Power Square description are a number of commands, with each command on a separate line. Each command begins with the name of the command, followed by any additional command parameters.
There will no more than 100 commands.

Input is a description of of the Power Square, followed by a number of commands. The first line is the size of the Power Square n. You may assume n<=100. The second line contains the n2 values in the Power Square, separated by spaces. Values start from the top left corner and move from left to right, moving down one row to the leftmost position when a row is filled.
Following the Power Square description are a number of commands, with each command on a separate line. Each command begins with the name of the command, followed by any additional command parameters.
There will no more than 100 commands.

3
8 7 6 5 4 3 2 1 0
SHOW
MOVE up
SHOW
3
8 7 6 5 4 3 2 1 0
SHOW
MOVE up right

8 7 6
5 4 3
2 1 0

MOVED
8 7 6
5 4 0
2 1 3

8 7 6
5 4 3
2 1 0

FAILED

#include<stdio.h>
#include<string.h>
char s[10000];
int map[111][111];
int main()
{
int n,i,j,flag=0,x,y,xx,yy,cg;//cg表示交换是否成功  flag表示输入是否依旧是up right down left
while(scanf("%s",s)!=EOF)
{
if(strcmp(s,"MOVE")==0)
{
if(flag==1)
{
if(cg==1) printf("MOVED\n");
else printf("FAILED\n");
cg=1;
flag=0;
}
}
else if(strcmp(s,"SHOW")==0)
{

if(flag==1)
{
if(cg==1) printf("MOVED\n");
else printf("FAILED\n");
cg=1;
flag=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<n;j++)
printf("%d ",map[i][j]);
printf("%d\n",map[i][j]);
}
printf("\n");
}
else if(strcmp(s,"up")==0)
{
if(cg==0) continue;
flag=1;
xx=x-1;yy=y;
if(xx<1||xx>n||yy<1||yy>n) cg=0;
else
{
int temp;
temp=map[x][y];map[x][y]=map[xx][yy];map[xx][yy]=temp;
//temp=x; x=xx;xx=temp; temp=y; y=yy;yy=temp;
x=xx;y=yy;
}
}
else if(strcmp(s,"left")==0)
{
if(cg==0) continue;
flag=1;
xx=x;yy=y-1;
if(xx<1||xx>n||yy<1||yy>n) cg=0;
else
{
int temp;
temp=map[x][y];map[x][y]=map[xx][yy];map[xx][yy]=temp;
//temp=x; x=xx;xx=temp; temp=y; y=yy;yy=temp;
x=xx;y=yy;
}
}
else if(strcmp(s,"right")==0)
{
if(cg==0) continue;
flag=1;
xx=x;yy=y+1;
if(xx<1||xx>n||yy<1||yy>n) cg=0;
else
{
int temp;
temp=map[x][y];map[x][y]=map[xx][yy];map[xx][yy]=temp;
//temp=x; x=xx;xx=temp; temp=y; y=yy;yy=temp;
x=xx;y=yy;
}
}
else if(strcmp(s,"down")==0)
{
if(cg==0) continue;
flag=1;
xx=x+1;yy=y;
if(xx<1||xx>n||yy<1||yy>n) cg=0;
else
{
int temp;
temp=map[x][y];map[x][y]=map[xx][yy];map[xx][yy]=temp;
//temp=x; x=xx;xx=temp; temp=y; y=yy;yy=temp;
x=xx;y=yy;
}
}
else
{
if(flag==1)
{
if(cg==1) printf("MOVED\n");
else printf("FAILED\n");
}
flag=0;
n=0;cg=1;
//printf("s=%s\n",s);
for(i=0;s[i]!='\0';i++) n=n*10+s[i]-'0';
// printf("n=%d\n",n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==0) {x=i;y=j;}
}
}
}
if(flag==1)//如果最后一个命令是MOVE  要在所有输入结束后输出下面的结果
{
if(cg==1) printf("MOVED\n");
else printf("FAILED\n");
}

}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……