| ||||||||||
| 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