noj 1058 Tom and Jerry

最新推荐文章于 2022-03-27 19:57:59 发布

雨狮子

最新推荐文章于 2022-03-27 19:57:59 发布

阅读量615

点赞数

分类专栏： ACM_搜索文章标签： noj

本文链接：https://blog.csdn.net/CriminalCode/article/details/50683119

版权

ACM_搜索专栏收录该内容

32 篇文章

订阅专栏

这是一个关于Tom和Jerry在10*10方格中移动的编程问题，目标是计算他们相遇所需的时间。题目描述了他们的移动规则和障碍物分布，并给出了样例输入和输出。解题方法为深度优先搜索（DFS），考虑了旋转方向和已访问位置的标记，避免死循环。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Tom and Jerry
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 257 测试通过 : 103
比赛描述
Tom和Jerry在10*10的方格中：
……..
……*…
……..
……….
…*.C….
…..…
…*……
..M……*
….….
..……

C=Tom（猫）
M=Jerry（老鼠）
*=障碍物
.=空地

他们各自每秒中走一格，如果在某一秒末他们在同一格中，我们称他们“相遇”。注意，“对穿”是不算相遇的。
他们移动方式相同：平时沿直线走，下一步如果会走到障碍物上去或者出界，就用1秒的时间做一个右转90度。一开始他们都面向北方。
编程计算多少秒以后他们相遇。

输入
10行，格式如上

输出

相遇时间T。如果无解，输出-1。

样例输入
……..
……*…
……..
……….
…*.C….
…..…
…*……
..M……*
….….
..……

样例输出
49

题目来源
wwm

题目链接：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1058

解题思路：
简单的深搜，因为Tom和Jerry的旋转方向是规定的，因此不用考虑最短时间的问题，dfs传递了7个参数，前四个分别代表Tom和Jerry的当前位置坐标，接着分别是Tom和Jerry的当前方向，最后一个是时间。当能走下一步时方向不改变，不能走时方向改变，只有时间是每进入一层＋1的。关键是访问过的情况标记，我用了四位数组，只有当Tom和Jerry的位置和方向全部相同是才标记。

代码如下：

#include <cstdio>
#include <cstring>
char s[12][12];
int vis[100][100][4][4];
int scx,scy,smx,smy;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int ans;
bool p,q;
void dfs(int cx,int cy,int mx,int my,int dc,int dm,int cnt)
{
    if(cx==mx && cy==my)
    {
        ans=cnt;
        p=true;
        return ;
    }
    int ncx=cx+dx[dc];
    int ncy=cy+dy[dc];
    if(ncx<0 || ncx>=10 || ncy<0 || ncy>=10 || s[ncx][ncy]=='*')
    {
        if(dc+1>=4)
            dc=0;
        else 
            dc+=1;
        ncx=cx;
        ncy=cy;
    }
    int nmx=mx+dx[dm];
    int nmy=my+dy[dm];
    if(nmx<0 || nmx>=10 || nmy<0 || nmy>=10 ||s[nmx][nmy]=='*')
    {
        if(dm+1>=4)
            dm=0;
        else 
            dm+=1;
        nmx=mx;
        nmy=my;
    }
    if(vis[ncx*10+ncy][nmx*10+nmy][dc][dm])
    {
        return;
    }
    vis[ncx*10+ncy][nmx*10+nmy][dc][dm]=1;
    dfs(ncx,ncy,nmx,nmy,dc,dm,cnt+1);
    if(p)
        return ;
    vis[ncx*10+ncy][nmx*10+nmy][dc][dm]=0;
}
int main(void)
{
    ans=0;
    p=false,q=false;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<10;i++)
    {
        scanf("%s",s[i]);
        for(int j=0;j<10;j++)
        {
            if(s[i][j]=='C')
            {
                scx=i;
                scy=j;
            }
            else if(s[i][j]=='M')
            {
                smx=i;
                smy=j;
            }
        }
    }
    if(smx==scx && scy==smy)
    {
        printf("0\n");
        return 0;
    }
    dfs(scx,scy,smx,smy,0,0,0);
    if(p)
        printf("%d\n",ans);
    else
        printf("-1\n");
}