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

暴力枚举DFS水过 282ms

Posted by Ren_Bocheng at 2015-10-18 15:15:54 on Problem 1753
#include<stdio.h>
#include<string.h>

int step,flag,mmap[5][5];
int dir[5][2] = {-1,0, 1,0, 0,0, 0,-1, 0,1};

int check()
{
    for(int i = 0; i < 4; ++i)
        for(int j = 0; j < 4; ++j)
            if(mmap[i][j]!=mmap[0][0])
                return 0;
    return 1;
}

void flip(int x, int y)
{
    for(int i = 0; i < 5; ++i)
    {
        int xx = x+dir[i][0];
        int yy = y+dir[i][1];
        if(xx >= 0&&xx < 4&&yy >= 0&&yy < 4)
            mmap[xx][yy] = !mmap[xx][yy];
    }
}

void dfs(int x, int y, int deep)
{
    if(deep==step)
    {
        flag = check();
        return ;
    }
    if(x==4||flag)return ;
    flip(x, y);
    if(y==3)
    {
        dfs(x+1, 0, deep+1);
        flip(x, y);
        dfs(x+1, 0, deep);
    }
    else
    {
        dfs(x, y+1, deep+1);
        flip(x, y);
        dfs(x, y+1, deep);
    }
    return ;
}

int main()
{
    char s[5];
    while(~scanf("%s", s))
    {
        for(int i = 0; i < 4; ++i)
            mmap[0][i] = (s[i]=='b'?1:0);
        for(int i = 1; i < 4; ++i)
        {
            scanf("%s", s);
            for(int j = 0; j < 4; ++j)
                mmap[i][j] = (s[j]=='b'?1:0);
        }
        flag = 0;
        for(step = 0; step < 17; ++step)
        {
            dfs(0, 0, 0);
            if(flag)break;
        }
        flag?printf("%d\n", step):printf("Impossible\n");
    }
    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