Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WA了n发,内存爆了无数次,终于A了!

Posted by swjtu_acm at 2020-07-05 00:19:05 on Problem 1324
/*
内存爆的原因开始是因为没有用状态压缩,直接用数组表示贪吃蛇,内存过大,
改了之后任然爆,是因为没有用vis标记已访问点,
WA了n多次是因为vis标记数组应该在新的状态下判断,而不是队头的状态(估计只有我这种菜鸡才会犯这个错吧),
看下我的代码吧,写的很凌乱,将就看。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue> 
using namespace std;
bool map[21][21];//地图
bool vis[21][21][1<<14];
typedef struct
{
    int x,y;        //坐标
    int state;      //蛇身状态
    int step;       //走的步数
}Point;
int dxy[4][2]={
    1,0,    //下
    -1,0,   //上
    0,1,    //右
    0,-1    //左
};
int m,n,L,K;
int beginState;
int headx,heady;
// 广度优先搜索
int bfs()
{
    queue<Point>P;
    Point root;//根
    memset(vis,0,sizeof(vis));
    root.state = beginState;
    root.step=0;
    root.x = headx;root.y=heady;
    P.push(root);
    while (!P.empty())
    {
        Point f = P.front();
        if(f.x==1&&f.y==1)
            return f.step;//达到目的地,结束
        for(int i=0;i<4;i++){
            int dx=f.x+dxy[i][0];// 新的坐标点
            int dy=f.y+dxy[i][1];
            int tx=f.x,ty=f.y;
            bool pass = false;
            for(int k=L-2;k>=0;k--)
            {   //当前点是蛇身体
                tx+=dxy[(f.state>>(2*k))%4][0];
                ty+=dxy[(f.state>>(2*k))%4][1];
                if(dx==tx&&dy==ty){
                    pass = true;
                    break;
                }
            }
            if(pass||dx<=0||dx>n||dy<=0||dy>m||map[dx][dy])
                continue;
            Point newHead=f;
            newHead.x = dx;
            newHead.y = dy;
            newHead.step = f.step+1;//步数加一
            //更新蛇头,丢掉蛇尾
            newHead.state = ((i/2*2+(!(i%2)))<<(2*L-4))+(newHead.state>>2);
            if(!vis[dx][dy][newHead.state])
            {
                P.push(newHead);
                vis[dx][dy][newHead.state]=1;
            }
        }
        P.pop();//队头出队
    }
    return -1;//不能达到终点 
}
int main()
{
    int cnt=1;
    int x,y;
    while (cin>>n>>m>>L){
        beginState=0;
        if(n==0&&m==0&&L==0)break;
        memset(map,0,sizeof(map));
        for(int i=0;i<L;i++){
            int dx,dy;
            cin>>dx>>dy;
            if(i==0){
                headx = dx;
                heady = dy;
            }else{
                for(int k=0;k<4;k++){
                    if(((dx-x)==dxy[k][0])&&((dy-y)==dxy[k][1])){
                        beginState<<=2;
                        beginState += k;
                    }
                        
                }
            }
            x=dx;y=dy;
        }
        cin>>K;
        for(int i=0;i<K;i++)
        {
            cin>>x>>y;
            map[x][y]=true;//表示障碍
        }
        cout<<"Case "<<cnt++<<":"<<" ";
        cout<<bfs()<<endl;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator