洛谷 P1518 农民找牛
作者:
quiet_
,
2023-04-06 23:40:23
,
所有人可见
,
阅读 136
//1.读入图的同时 获得 farmer cow 的坐标
//2.定义一个方向数组 按照 以北为初始 顺时针的顺序 并分别定义两个量 用来确定此时的方向
//3.判断该方向是否可以走 如果可以走 更新坐标 不可以走 方向 ++ 每进行一次循环 cnt++ 循环进行的条件是还没有相遇
// 如何判断进入了死循环?
//a. 超过一定次数 最多就有160000次 对于farmer来说 100个点每个点4个方向 400 对于cow来说也是一样的 一共160000次
//b. 经过一个点两边即可判定进入了死循环 按照这个思路我们对每一种可能的情况幅一个特征值 如果在某次循环中这个特征值以前出现过 那么就证明进入了死循环
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
char g[N][N];
int cnt;
int main()
{
pair<int,int> cow, farmer;
for(int i = 0 ; i < 10 ; i ++)
{
for(int j = 0 ; j < 10 ; j ++)
{
char c;
cin >> c;
g[i][j] = c;
if(c == 'F') farmer = {i , j};
else if(c == 'C') cow = {i , j};
}
}
int dircow = 0, dirfa = 0;
int dx[4] = {-1 ,0 ,1 ,0};
int dy[4] = {0 ,1 ,0 ,-1};
int xf,yf,xc,yc;
xf = farmer.first, yf = farmer.second, xc = cow.first, yc = cow.second;
while(xf != xc || yf != yc)
{
if(g[xf + dx[dirfa]][yf + dy[dirfa]] != '*' && xf + dx[dirfa] >= 0 && xf + dx[dirfa] < 10 && yf + dy[dirfa] >= 0 && yf + dy[dirfa] < 10)
{
xf = xf + dx[dirfa];
yf = yf + dy[dirfa];
}
else
{
dirfa ++;
dirfa = dirfa % 4;
}
if(g[xc + dx[dircow]][yc + dy[dircow]] != '*' && xc + dx[dircow] >= 0 && xc + dx[dircow] < 10 && yc + dy[dircow] >= 0 && yc + dy[dircow] < 10)
{
xc = xc + dx[dircow];
yc = yc + dy[dircow];
}
else
{
dircow ++;
dircow = dircow % 4;
}
cnt ++;
if(cnt > 160000)
{
printf("0");
return 0;
}
}
printf("%d",cnt);
return 0;
}