NEERC, Northern Subregional Contest 2012 B 乱搞or搜索

题意:给你10×10的格子有 1艘 4格的船， 2艘3格的，3艘2格的，4艘1格的。每艘船只能横着或者竖着，但是不能相邻（叫相邻也不行）现在给你每个格子的攻击时间，有且仅有所有船下面所有的格子都被攻击以后，船沉没，当所有格子沉没以后，测试结束，问你结束的最长时间是多少。

解题思路：把100那个位置覆盖掉，搜索或者直接填都行。

解题代码：

  1 // File Name: 12906.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年08月17日 星期日 14时16分54秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 
 26 using namespace std;
 27 int mp[20][20];
 28 int check(int i,int j)
 29 {
 30     int sum = 0 ;
 31     if(i <= 10 && i >= 1 && j <= 10 && j >=1 )
 32     {
 33        sum += mp[i+1][j] + mp[i][j] + mp[i-1][j] +mp[i][j+1] + mp[i][j-1] + mp[i+1][j+1] + mp[i+1][j-1] + mp[i-1][j+1] + mp[i-1][j-1] ;
 34        if(sum == 0 )
 35          return 1;
 36         return 0 ; 
 37     }
 38     return 0 ;
 39 }
 40 int ship[] = {0,4,3,3,2,2,2,1,1,1,1};
 41 int hs[20];
 42 int dfs(int x, int y , int k ,int dis)
 43 {
 44    if(k == 1 )
 45        return  1;
 46    if(dis == 1)
 47    {
 48       int tx = x + 1; 
 49       int ty = y;
 50       if(check(tx,ty))
 51       {
 52           if(dfs(tx,ty,k-1,dis))
 53           {
 54              mp[tx][ty] =1 ;
 55              return 1;
 56           }
 57       }else{
 58           return 0 ; 
 59       }
 60    }else if(dis == 2){
 61       int tx = x -1; 
 62       int ty = y;
 63       if(check(tx,ty))
 64       {
 65           if(dfs(tx,ty,k-1,dis))
 66           {
 67              mp[tx][ty] =1 ;
 68              return 1;
 69           }
 70       }else{
 71           return 0 ; 
 72       }
 73    
 74    }else if(dis == 3){
 75       int tx = x; 
 76       int ty = y+1;
 77       if(check(tx,ty))
 78       {
 79           if(dfs(tx,ty,k-1,dis))
 80           {
 81              mp[tx][ty] =1 ;
 82              return 1;
 83           }
 84       }else{
 85           return 0 ; 
 86       }
 87    
 88    }else {
 89       int tx = x; 
 90       int ty = y-1;
 91       if(check(tx,ty))
 92       {
 93           if(dfs(tx,ty,k-1,dis))
 94           {
 95              mp[tx][ty] =1 ;
 96              return 1;
 97           }
 98       }else{
 99           return 0 ; 
100       }
101    
102    }
103    return 0 ;
104 }
105 void solve(int x, int y )
106 {
107    //printf("%d %d
",x,y);
108    for(int i = 1;i <= 9 ;i ++)
109        if(hs[i] == 0 )
110        for(int j = 1;j <= 4 ;j ++)
111        {
112            if(dfs(x,y,ship[i],j))
113            { 
114                mp[x][y] = 1;
115                hs[i] = 1; 
116                return ;
117            }
118        }
119 }
120 int main(){
121     int temp ; 
122     while(scanf("%d",&temp) != EOF)
123     {
124         memset(mp,0,sizeof(mp));
125         memset(hs,0,sizeof(hs));
126         if(temp == 100 )
127         {
128             mp[1][1] = 1; 
129         }
130         for(int  i = 2;i <= 10;i ++)
131         {
132             scanf("%d",&temp);
133             if(temp == 100 )
134             {
135                 mp[1][i] = 1; 
136             }
137         }
138         for(int i = 2;i <= 10;i ++)
139         {
140 
141             for(int j = 1;j <= 10; j ++)
142             {
143                 scanf("%d",&temp);
144                 if(temp == 100 )
145                 {
146                    mp[i][j] = 1; 
147                 }
148             }
149         }
150         for(int i =1;i <= 10;i ++)
151         {
152            for(int j = 1;j <= 10; j ++)
153            {
154               if(check(i,j))
155               {
156                   solve(i,j);
157               }
158            }
159         }
160         for(int i =1;i <= 10 ;i ++)
161         {    for(int j = 1;j <= 10 ;j ++)
162             {
163               if(mp[i][j])
164               {
165                 printf("#");
166               }else printf(".");
167             }
168             printf("
");
169         }
170     }
171     return 0;
172 }

View Code

没有梦想，何谈远方