题解 P1518 【两只塔姆沃斯牛 The Tamworth Two】

早右昕 · 2017-12-03 17:30:13 · 题解

An amazing Tijie.其实我是来水贡献的

完全没有把题做得很复杂的必要，我通过以下几个方面来精简代码以及维护可读性：

• 使用struct维护状态，定义俩操作
• 把地图越界的地方都看作障碍
• 判无解，数据服务小可以使用vis[i][j][k][l]来表示（i,j),(k,l)的次数，若大于4，很明显至少有两次方向一样==>无解

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
struct one { int x,y,face; };
char map[12][12];
int vis[11][11][11][11];
void operator++(one& a) {
    int nx=a.x+dx[a.face];
    int ny=a.y+dy[a.face];
    if(map[nx][ny]!='\*') a.x=nx,a.y=ny;
    else a.face++,a.face%=4;
}
bool operator!=(const one&a,const one&b) {
    return a.x!=b.x||a.y!=b.y;
}
int main(){
    one jhon,cow;
    fill(map[0],map[0]+12,'\*');
    fill(map[11],map[11]+12,'\*');
    for(int i=1;i<=10;i++) {
        scanf("%s\n",&map[i][1]);
        map[i][0]=map[i][11]='\*';
        for(int j=1;j<=10;j++) {
            if(map[i][j]=='C') cow=(one) {i,j,0};
            if(map[i][j]=='F') jhon=(one) {i,j,0};
        }
    }
    int ans=0;
    while(jhon!=cow) {
        if(vis[jhon.x][jhon.y][cow.x][cow.y]++==4) {
            printf("0");
            return 0;
        }
        ans++,++jhon,++cow;
    }
    printf("%d\n",ans);
    return 0;
}

至此，问题以完美解决。