题目1 : 推箱子
时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB描述
推箱子是一款经典游戏。如图所示，灰色格子代表不能通过区域，蓝色方格是箱子，黑色圆形代表玩家，含有圆点的格子代表目标点。
规定以下规则：
1、一局游戏中只会有一个箱子，一个玩家和一个目标点。
2、通过方向键控制玩家移动。
3、图中的灰色格子代表墙壁，玩家与箱子都不能通过。
4、推到墙壁的箱子，就无法再将箱子推离墙壁，因为玩家无法到达箱子靠墙壁的一侧去推箱子。也就是说箱子只能以“被推”的方式被移动，不是以“被拉”的方式被移动。但如果玩家将箱子推至墙壁后，垂直墙壁的两侧没有阻碍物，则玩家可以朝这两个不同的方向推移箱子。如果箱子进入角落，就没有办法再推动这个箱子了。
5、玩家是不能走出场景的。玩家推着箱子到达场景边缘，如果继续点击使玩家和箱子向墙壁前进的方向键，箱子和人都会保持不动。玩家的前进方向上如果有墙壁，也是不能前进的。但是这些点击都视为合理的输入。
6、箱子一旦到达目标点，就不能再移动了。但这时，玩家仍然可以在场景内自由行动。如果继续尝试推箱子，那么玩家将会和箱子一起保持在原地不动。
现在，给出一种方向键的点击方案，请判断，这种方案是否能使箱子最终停在目标点上。为了方便表示，我们以0代表空白格子，以4代表不能通过区域，以1代表玩家，以3代表箱子，以2代表目标点。
输入
第一行数据包含三个整数，N，M，S。其中，N(0 < N <= 100)代表格子的宽度，M(0 < M <= 100)代表格子的高度，S(0 < S <= 200)代表测试点的个数。
接下来的M行，每行都会有N个字符，描述当前的盘面。
接下来的S行，每行都代表一个测试点。每行都以一个整数T(0 < T <= 10000)开头，接下来是一个空格和T个字符。这T个字符仅由d，u，l，r这四个字母组成，分别代表了敲击向下，向上，向左，向右的方向键。
输出
对于每个测试点，输出最后箱子是否在目标点上。如果是，输出YES，如果不是，则输出NO。
样例输入
5 4 3000001300000200000004 rurd6 urdldr6 rrrurd
样例输出
YESYESNO
我的AC代码，很直接的思路
#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct Node{int ha,li;};char gezi[105][105];char cz[10010];int n,m,s;int wjh=0,wjl=0;int xzh=0,xzl=0;int mbh=0,mbl=0;int fangx(Node wanj,Node xiangz);void solve(Node wanj,Node xiangz);int main(){//freopen("wyin1.in","r",stdin);//freopen("wyout1.out","w",stdout);scanf("%d%d%d",&n,&m,&s);for(int i=0;i<m;++i){scanf("%s",gezi[i]);for(int j=0;j<strlen(gezi[i]);++j){if(gezi[i][j]=='1'){wjh=i;wjl=j; gezi[i][j]='0';}else if(gezi[i][j]=='2'){mbh=i;mbl=j;gezi[i][j]='0';}else if(gezi[i][j]=='3'){xzh=i;xzl=j; gezi[i][j]='0';}}}int t;for(int i=0;i<s;++i){scanf("%d",&t);scanf("%s",cz);Node wj={wjh,wjl};Node xz={xzh,xzl};solve(wj,xz);}//system("pause");return 0;}void solve(Node wanj,Node xiangz){int flag=0;//printf("cz:%s\n",cz);for(int i=0;i<strlen(cz);++i){if(cz[i]=='u'){if(fangx(wanj,xiangz)==3)//玩家在下边{if(xiangz.ha>0 && (gezi[xiangz.ha-1][xiangz.li]=='0'||gezi[xiangz.ha-1][xiangz.li]=='2')){xiangz.ha--;wanj.ha--;} }else if(wanj.ha>0 && (gezi[wanj.ha-1][wanj.li]=='0'||gezi[wanj.ha-1][wanj.li]=='2')){wanj.ha--; }}else if(cz[i]=='d'){if(fangx(wanj,xiangz)==2)//玩家在上边{if(xiangz.ha<m-1 && (gezi[xiangz.ha+1][xiangz.li]=='0'||gezi[xiangz.ha+1][xiangz.li]=='2')){xiangz.ha++;wanj.ha++;}}else if(wanj.ha<m-1 && (gezi[wanj.ha+1][wanj.li]=='0'||gezi[wanj.ha+1][wanj.li]=='2')){wanj.ha++; }}else if(cz[i]=='l'){if(fangx(wanj,xiangz)==1)//玩家在右边{if(xiangz.li>0 && (gezi[xiangz.ha][xiangz.li-1]=='0'||gezi[xiangz.ha][xiangz.li-1]=='2')){xiangz.li--;wanj.li--; }}else if(wanj.li>0 && (gezi[wanj.ha][wanj.li-1]=='0'||gezi[wanj.ha][wanj.li-1]=='2')){wanj.li--; }}else if(cz[i]=='r'){if(fangx(wanj,xiangz)==0)//玩家在左边 {if(xiangz.li<n-1 && (gezi[xiangz.ha][xiangz.li+1]=='0'||gezi[xiangz.ha][xiangz.li+1]=='2')){xiangz.li++;wanj.li++; }}else if(wanj.li<n-1 && (gezi[wanj.ha][wanj.li+1]=='0'||gezi[wanj.ha][wanj.li+1]=='2')){wanj.li++; }}if(xiangz.ha==mbh && xiangz.li==mbl){flag=1;break;}}if(flag) printf("YES\n");else printf("NO\n");}int fangx(Node wanj,Node xiangz){if(wanj.li==xiangz.li-1 && wanj.ha==xiangz.ha) return 0;//玩家在箱子左边else if(wanj.li==xiangz.li+1 && wanj.ha==xiangz.ha) return 1;//玩家在右边else if(wanj.li==xiangz.li && wanj.ha==xiangz.ha-1) return 2;//玩家在上边else if(wanj.li==xiangz.li && wanj.ha==xiangz.ha+1) return 3;//玩家在下边else return 4; }
