洛谷P1518两只塔姆沃斯牛

1. 题目描述

emm…原题太长

详细题目描述见原题地址

2. Notes

2.1. 数据捆绑

这次成功应用洛谷P1563玩具谜题2.1中的总结,人和牛的坐标及朝向这三个数据是时刻绑在一起的,是一个整体,因此可以考虑使用结构体来表示。(面向对象%_%)

2.2. 模拟(建模)思维

一切信息和条件的表示都用数字来表示(比如该题中的方向用0,1,2,3来表示),这样可以利用数学的知识来简化处理的过程(比如通过取余来表示顺时针方向改变)。

当然,具体怎么通过数值信息表达非数值信息需要一定的技巧,慢慢积累。总之,就是将非数值化的对象数值化,再找数量之间的关系。

2.3. 用取余来表示循环取值的数学本质

我们知道,任何一个正数$m$,对正数$n$做取余运算$m%n$的结果一定属于$\{0,1,2,…,n-1\}$这个集合。

因此,当我们需要在一个序列中循环取值的时候,比如对于$m,m+1,m+2,…,m+n-1$这由$n$个数组成的依次递增的序列,需要从$m$开始递增的取值,当达到$m+n-1$的时候下一个取序列中最小值$m$,那么便可以表达成

1
a = m + (a + 1) % n

其中a为当前取值。

解释:(a+1)%n会在$\{0,1,2,…,n-1\}$中取一个比a%n对应的值大1的数,但是遗憾的是只能表示从0开始计数的,而我们的序列是从$m$开始计数的,因此需要再加上$m$。

2.4. 读入矩阵

只能按行从标准输入读矩阵。因此,为统一起见,今后二维数组第一位表示行,第二位表示列。有边界的,就从i=1,j=1开始读。也就是说二维数组的矩阵布局和题目中的应是一样的,只是进行了数值化处理。

2.5. 细节问题

  1. switch别忘了break
  2. 提交时别忘了删cout之类的debug代码!!!

3. 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
struct xy{ //表示John和Cow
int x;
int y;
int face;//朝向 0123上右下左 便于顺时针旋转取余
};
int main(){
char map[12][12];
struct xy john,cow,tmp;
char c;
int i,j,times=0;//i代表行 j代表列
//初始化地图
memset(map,1,sizeof(map));
//录入地图数据和两点坐标
for(i=1;i<=10;i++){
for(j=1;j<=10;j++){
cin>>c;
if(c=='.'){
map[i][j]=0;
}else if(c=='C'){
cow.x=i; cow.y=j;
cow.face=0;
map[i][j]=0;
}else if(c=='F'){
john.x=i; john.y=j;
john.face=0;
map[i][j]=0;
}
}
}

while(john.x!=cow.x||john.y!=cow.y){
//直接冲,遇到障碍物再退回来
tmp.x=john.x;tmp.y=john.y;
switch(john.face){
case 0: john.x--; break;
case 1: john.y++; break;
case 2: john.x++; break;
case 3: john.y--;
}

if(map[john.x][john.y]){
john.x=tmp.x;john.y=tmp.y;
john.face=(john.face+1)%4;
}
//同John
tmp.x=cow.x;tmp.y=cow.y;
switch(cow.face){
case 0: cow.x--; break;
case 1: cow.y++; break;
case 2: cow.x++; break;
case 3: cow.y--;
}
if(map[cow.x][cow.y]){
cow.x=tmp.x;cow.y=tmp.y;
cow.face=(cow.face+1)%4;
}

times++;
if(times>=600000){ //次数足够大退出,骗分$_$
times=0;
break;
}
}
cout<<times;
return 0;
}