题解 - 洛谷 P1518 两只塔姆沃斯牛
Published:
思路
基本想法
一看就知道是一道模拟题，由于每次行走到的点都是确定的，我们只需要（暴力地）枚举出这次到达的点并且判断是否相遇。
重点问题：如何判断是否有解
这里我想到一个十分巧(pian)妙(fen)的方法。上面的枚举次数如果超过 60 万那肯定就无解了，所以在上面的循环只要使 i 从 1 到 600000，如果找到有解，立刻输出并终止程序。
PS：60 万这个数字是我随便报的，可能评测机一秒内也就只能运算 70 万~100 万次左右吧嘤嘤嘤
代码
#include <iostream>
#include <string>
#include <utility>
using namespace std;
int op[4][2] = { //四种操作，由题意，这里必须顺时针排
{-1, 0}, //0-向上
{0, 1}, //1-向右
{1, 0}, //2-向下
{0, -1} //3-向左
};
bool no[12][12];//记录某个位置是否有障碍物(true是有障碍物)
pair<int, int> sb, cow;//sb-FarmerJohn的位置,cow-牛的位置
int dirsb = 0, dircow = 0; //二人面向的方向
int ans = 0;
int main()
{
//输入
string x[11];
for (int i = 1; i <= 10; i++) {
cin >> x[i];
for (int j = 0; j < 10; j++) {
//有障碍物
if (x[i][j] == '*') {
no[i][j + 1] = true;
} else if (x[i][j] == 'F') {
sb = make_pair(i, j + 1); //FJ的位置
} else if (x[i][j] == 'C') {
cow = make_pair(i, j + 1);//牛的位置
}
}
}
//棋盘四周都是障碍物
for (int i = 0; i <= 11; i++) {
no[0][i] = no[11][i] = true;
}
for (int i = 0; i <= 11; i++) {
no[i][0] = no[i][11] = true;
}
for (int i = 1; i <= 600000; i++) {
ans++; //步数+1
//记录新的位置
pair<int, int> newsb, newcow;
newsb = make_pair(sb.first + op[dirsb][0], sb.second + op[dirsb][1]);
newcow = make_pair(cow.first + op[dircow][0], cow.second + op[dircow][1]);
//如果有障碍物或没有
if (no[newsb.first][newsb.second]) dirsb = (dirsb + 1) % 4;
else sb = newsb;
if (no[newcow.first][newcow.second]) dircow = (dircow + 1) % 4;
else cow = newcow;
//如果相遇
if (sb == cow) {
cout << ans << endl;
return 0;
}
}
cout << 0 << endl;
return 0;
}