本文共 2899 字，大约阅读时间需要 9 分钟。
题意:给你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 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 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\n",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("\n");169 }170 }171 return 0;172 }
转载于:https://www.cnblogs.com/zyue/p/3918855.html
