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

简单的BFS,就是状态压缩一下就行了【43ms】

Posted by ssdut_201392326 at 2014-02-23 15:35:53 on Problem 1753
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

int op[5][5];
bool vis[70000];
queue<int> xx;
int dx[4]={1,-1,0,0},
    dy[4]={0,0,1,-1};

bool ok(int x,int y)
{
    if(x>=0&&x<4&&y>=0&&y<4)
        return 1;
    return 0;
}

int bfs(int st)
{
    while(!xx.empty())xx.pop();
    int step=0,cur,i,j,k;
    xx.push(st);
    while(!xx.empty())
    {
        int t=xx.size();
        while(t--)
        {
            cur=xx.front();
            xx.pop();
            vis[cur]=1;
            if(cur==0||cur==65535)
                return step;
            else
            {
                int next;
                for(i=0;i<4;i++)
                {
                    for(j=0;j<4;j++)
                    {
                        next=cur^op[i][j];
                        for(k=0;k<4;k++)
                        {
                            int tx,ty;
                            tx=i+dx[k];
                            ty=j+dy[k];
                            if(ok(tx,ty))
                                next=next^op[tx][ty];
                        }
                        if(!vis[next])
                        {
                            xx.push(next);
                            vis[next]=1;
                        }
                    }
                }
            }

        }
        step++;
    }
    return -1;
}

int input()
{
    memset(op,0,sizeof(op));
    memset(vis,0,sizeof(vis));
    int ans=0,cc=0;
    char grid[5][5];
    int i,j;
    for(i=0;i<4;i++)
        scanf("%s",grid[i]);
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
        {
            op[i][j]=pow(2,cc);
            if(grid[i][j]=='w')
                ans+=pow(2,cc);
            cc++;
        }
    return ans;
}

int main()
{
    int start,i,j;
    start=input();
    int ans=bfs(start);
    if(ans==-1)
        cout<<"Impossible"<<endl;
    else
        cout<<ans<<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