如题:广度优先搜索
#include < stdio.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int hash[105][105];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int l, c;
}type;
type q[50000];
int head, tail;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int move[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inith( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
hash[i][j] = 0;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initq()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
head = 0;
tail = -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inq( type *a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
tail ++;
q[tail].l = a->l;
q[tail].c = a->c;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void outq( type *a )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
a->l = q[head].l;
a->c = q[head].c;
head ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int testempty()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if( head > tail )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return 1;
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int bfs( type *s, int cor, int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ans = 0;
int tl, tc;
type a, b;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
initq();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
inq( s );
ans ++;
hash[s->l][s->c] = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( ! testempty() )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
outq( &a );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<4; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tl = a.l + move[i][0];
tc = a.c + move[i][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( tl>=0 && tl<n && tc>=0 && tc<n && hash[tl][tc]==cor )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
b.l = tl;
b.c = tc;
inq( &b );
ans ++;
hash[tl][tc] = -1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n;
char ch;
type in;
int i, j;
while ( 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf( "%d%c", &n, &ch );
if ( n==0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
inith( n );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<n-1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int x, y;
scanf( "%d%d", &x, &y );
hash[x-1][y-1] = i + 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( j=0; j<n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( hash[i][j] != -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
in.l = i;
in. c = j;
if ( bfs( &in, hash[i][j], n ) != n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
}
}
if ( j < n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
break;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( i<n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "wrong\n" );
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "good\n" );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|