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+BFS+非递归算法

Posted by xianghong at 2013-11-28 17:14:16 on Problem 2308
#include <stdio.h>
#include <string.h>

#define MAXROW 10
#define MAXCOL 10

typedef enum DIRECTION
{
    LEFT = 0,
    RIGHT,
    UP,
    DOWN,
    DIRECTIONNUM
}e_DIRECTION;

typedef struct t_position
{
    int x;
    int y;
}T_Position;

typedef struct t_same_set
{
    T_Position   positions[MAXROW*MAXCOL];
    unsigned int cnt;
}T_Same_Set;

typedef struct node
{
    T_Position     pos;
    unsigned int   directnum;
}T_Node;

T_Position directs[DIRECTIONNUM] = 
{
    {-1,0},
    {1,0},
    {0,1},
    {0,-1}
};

typedef struct t_search_queue
{
    unsigned char visited[MAXROW][MAXCOL];
    T_Node   path[MAXROW*MAXCOL+1];
    unsigned int  head;
    unsigned int  tail;
}T_Search_Queue;

typedef struct t_state
{
    int cnt;
    int i;
    int j;
    int k;
    int x;
    int y;
    int kind;
    int index;
    T_Same_Set set;
}T_State;

char               arr[MAXROW][MAXCOL] = {0};
T_Search_Queue     searchQueue = {0};
int                flag = 0;
int                kindcnt[4] = {0};
T_State            state[MAXROW*MAXCOL] = {0};
int                top = 0;

int isStateEmpty()
{
    return (top==0);
}

int pushstate(int cnt,
    int i,
    int j,
    int k,
    int x,
    int y,
    int kind,
    int index,
    T_Same_Set *pset)
{
    if (top >= MAXROW*MAXCOL)
        return -1;
    state[top].cnt = cnt;
    state[top].i = i;
    state[top].j = j;
    state[top].k = k;
    state[top].x = x;
    state[top].y = y;
    state[top].kind = kind;
    state[top].index = index;
    memcpy(&state[top].set,pset,sizeof(T_Same_Set));
    top++;
    return 0;
}

int popstate(int *cnt,
    int *i,
    int *j,
    int *k,
    int *x,
    int *y,
    int *kind,
    int *index,
    T_Same_Set *pset)
{
    if (top == 0)
        return -1;
    top--;
    *cnt  = state[top].cnt;    
    *i    = state[top].i;      
    *j    = state[top].j;      
    *k    = state[top].k;      
    *x   = state[top].x;      
    *y    = state[top].y;      
    *kind = state[top].kind;   
    *index = state[top].index;  
    memcpy(pset,&state[top].set,sizeof(T_Same_Set));
    return 0;
}

int isNoSolution(int row,int col,char card1, char card2) 
{     
    int i = 0;
    int j = 0;
    for(i = 0; i < row; i++) 
    {         
        for(j = 0; j < col; j++) 
        {             
            if(arr[i][j] == card1) 
            {                 
                if(arr[i+1][j+1] == card1 && 
                   arr[i+1][j] == card2 && arr[i][j+1] == card2) 
                {                     
                    return 1;
                }
                return 0;
            } 
            if(arr[i][j] == card2) 
            {                 
                if(arr[i+1][j+1] == card2 && 
                   arr[i+1][j] == card1 && arr[i][j+1] == card1) 
                {                   
                    return 1;             
                }                     
                return 0;            
            }         
         }         
    } 
} 


int prune(unsigned int row,unsigned int col)
{
    char i = 0;
    char j = 0;

    for(i = 0; i < 3; i++) 
    {         
        for(j = i+1; j < 4; j++) 
        {
            if(kindcnt[i] == kindcnt[j] && kindcnt[i] == 2)
            {
                if (isNoSolution(row, col, 'A'+i, 'A'+j) == 1)
                {
                    return 1;
                }
            }
        }
    }

    return 0;
}

void enqueueSearch(T_Search_Queue* pQue, T_Node* pNode)
{
    if ((pQue->tail + 1)%(MAXROW*MAXCOL+1) == pQue->head)
    {
        return;
    }
    memcpy(&pQue->path[pQue->tail],pNode,sizeof(T_Node));
    pQue->tail = (pQue->tail+1)%(MAXROW*MAXCOL+1);
    return;
}

void dequeueSearch(T_Search_Queue* pQue, T_Node* pNode)
{
    if (pQue->head == pQue->tail)
    {
        return;
    }

    memcpy(pNode,&pQue->path[pQue->head],sizeof(T_Node));
    pQue->head = (pQue->head+1)%(MAXROW*MAXCOL+1);
    return;
}

int isEmptySearchQueue(T_Search_Queue* pQue)
{
    return (pQue->head == pQue->tail);
}

int find_same_card(int row,int col,int x,int y, T_Same_Set* pSet)
{
    int        i        = 0;
    T_Node     node     = {0};
    T_Position nextPos  = {0};
    T_Node     nextnode = {0};
    char       card     = 0;

    memset(&searchQueue,0,sizeof(searchQueue));
    memset(pSet,0,sizeof(T_Same_Set));

    card = arr[x][y];
    node.pos.x = x;
    node.pos.y = y;
    node.directnum = 0;
    searchQueue.visited[x][y] = 1;
    enqueueSearch(&searchQueue,&node);

    while(!isEmptySearchQueue(&searchQueue))
    {
        dequeueSearch(&searchQueue,&node);

        if (node.directnum >= 3)
        {
            continue;
        }        

        for (i = 0; i < DIRECTIONNUM; i++)
        {
            nextPos.x = node.pos.x;
            nextPos.y = node.pos.y;
            while(1)
            {
                nextPos.x = nextPos.x+directs[i].x;
                nextPos.y = nextPos.y+directs[i].y;
                
                if ((nextPos.x >= row)||(nextPos.x < 0)||
                    (nextPos.y >= col)||(nextPos.y < 0)||
					          (searchQueue.visited[nextPos.x][nextPos.y] == 1)||
                    ((arr[nextPos.x][nextPos.y]!='*')&&(arr[nextPos.x][nextPos.y] != card)))
                {
                    break;
                }
                
                if (arr[nextPos.x][nextPos.y]=='*')
                {
                    searchQueue.visited[nextPos.x][nextPos.y] = 1;
                    memcpy(&nextnode.pos,&nextPos,sizeof(T_Position));  
                    nextnode.directnum = node.directnum + 1;
                    enqueueSearch(&searchQueue,&nextnode);
                }
                else if (arr[nextPos.x][nextPos.y]==card)
                {
                    searchQueue.visited[nextPos.x][nextPos.y] = 1;        
                    pSet->positions[pSet->cnt].x = nextPos.x;
                    pSet->positions[pSet->cnt].y = nextPos.y;
                    pSet->cnt++;
                    break;
                }
            }
        }
    }
    
    return (pSet->cnt == 0);
}

int link_calc(int row,int col,int cnt)
{
    int i;
    int j;
    int k;
    int x;
    int y;
    int kind;
    int index;
    T_Same_Set set;
    
do_start:
    i = 0;
    j = 0;
    k = 0;
    x = 0;
    y = 0;
    kind = 0;
    index = 0;
    memset(&set,0,sizeof(set));	
	
    if (cnt == 0)
    {
        flag = 1; 
        goto do_finish;
    }

    if (flag == 1)
    {
        goto do_finish;
    }

    if (prune(row,col) == 1)
    {
        goto do_finish;
    }

    for (i = 0; i < row; i++,j=0)
    {
        for (j = 0; j < col; j++)
        {
           if (flag == 1) return 0;
           
           if (arr[i][j]=='*')
               continue;

           kind = arr[i][j];
           if (find_same_card(row,col,i,j,&set) == 0)
           {
               for (k = 0; k < set.cnt; k++)
               {
                   x = set.positions[k].x;
                   y = set.positions[k].y;
                   arr[i][j] = arr[x][y] = '*';
                   index = kind - 'A';
                   kindcnt[index]-=2;
                   //link_calc(row,col,cnt-1);
                   pushstate(cnt,i,j,k,x,y,kind,index,&set);
                   cnt--;
                   goto do_start;
do_retaddr:
                   arr[i][j] = arr[x][y] = kind;
                   kindcnt[index]+=2;
               }
           }
        }
    }

do_finish:
    if (!isStateEmpty())
    {
        popstate(&cnt,&i,&j,&k,&x,&y,&kind,&index,&set);
        goto do_retaddr;
    }
    return 0;
}

int main(void)
{
    unsigned int  row = 0;
    unsigned int  col = 0;
    unsigned int  i   = 0;
    unsigned int  j   = 0;
    unsigned char c;
    int           oodflag = 0;
    int           paircnt = 0;

    while(scanf("%u %u",&row,&col)!=EOF)
    {
        getchar();
        if (row == 0 && col == 0) break;

        memset(arr,0,sizeof(arr));
        memset(kindcnt,0,sizeof(kindcnt));
        oodflag = 0; 
        paircnt = 0;
        
        for (i = 0; i < row; i++)
        {
            for (j = 0; j < col; j++)
            {
                scanf("%c",&arr[i][j]);

                switch(arr[i][j])
                {
                    case 'A':
                        kindcnt[0]++;
                        break;
                    case 'B':
                        kindcnt[1]++;
                        break;
                    case 'C':
                        kindcnt[2]++;
                        break;
                    case 'D':
                        kindcnt[3]++;
                        break;
                    default:
                        break;
                };
            }
            getchar();
        }

        for (i = 0; i < 4; i++)
        {
            paircnt += kindcnt[i];
            if (kindcnt[i]%2!=0)
            {
                oodflag = 1;
                break;
            }
        }
        if (oodflag == 1)
        {
            puts("no");
        }
        else
        {
    	    paircnt = paircnt/2;
            flag = 0;
            top = 0;
            link_calc(row,col,paircnt);
            if (flag == 1)
                puts("yes");
            else
                puts("no");  
        }
    }
}

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