Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
DFS+BFS+非递归算法#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator