TOJ--1162---dfs(回溯)

高数隐隐感觉要挂 =-=

莫非是因为我要上黄金的原因。。。

几天没做题了这题还是很有意思的好久没做回溯了

然后当时很SB地忘记了这是回溯了就一下子做不来了

写了个dfs后就卡住了受不了 = - =

然后参考了别人的博客 --- 瞬间满血复活

直接贴下别人的吧想到了回溯就能做了

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int n;
 6 int cnt;
 7 char block[10][10];
 8 
 9 bool judge( int x , int y )
10 {
11     int i,j;
12     for( i=x-1 ; i>=0 ; i-- )
13     {
14         if( block[i][y]=='o' )
15             return false;
16         if( block[i][y]=='X' )
17             break;
18     }
19     for( j=y-1; j>=0; j-- )
20     {
21         if( block[x][j]=='o' )
22             return false;
23         if( block[x][j]=='X' )
24             break;
25     }
26     return true;
27 }
28 
29 void dfs( int k , int num)
30 {
31     int x=k/n;
32     int y=k%n;
33     if( k == n*n )
34     {
35         if( num > cnt)
36         {
37             cnt=num;
38         }
39     }
40     else
41     {
42         if( block[x][y]=='.' && judge( x , y) )
43         {
44             block[x][y]='o';
45             dfs( k+1 , num+1 );
46             block[x][y]='.';
47         }
48         dfs( k+1 , num );
49     }
50 }
51 
52 int main()
53 {
54     while( ~scanf("%d",&n) && n )
55     {
56         cnt=0;
57         for(int i=0; i<n ;i++)
58         {
59             scanf("%s",block[i] );
60         }
61         dfs( 0 , 0 );
62         printf("%d
",cnt);
63     } 
64 }

View Code

today:

　　你让我感觉像是你生活中的调味品

　　我其实不是这个意思

　　我还太自负了

just follow your heart