A.Cakeminator
题目大意：给你一个矩形蛋糕，它由r * c 个单元格组成，每个单元格要是空的，要么包含一个邪恶的草莓。你要按下面的要求去吃蛋糕：一、每次选择不包含任何邪恶草莓的一行或一列，并且所选的这一行或一列中至少包含一个以前没有吃到的单元格蛋糕。二、选择一行或一列后，吃光这一行或列中所有的蛋糕。让你求：最多能吃多少个单元格的蛋糕？
思路：要求最多能吃多少个单元格的蛋糕，只要找出哪些单元格的蛋糕吃不到即可。方法如下：在矩形蛋糕中寻找所有邪恶草莓的位置，并将它们所在的行和列均做标记，然后得出: 不能吃的蛋糕数目 == 标记过的行的数目 * 标记过的列的数目， 最后 用 r * c —不能吃的蛋糕的数目 即可。请看代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std ;
int visx[15] ; // 用于标记行
int visy[15] ; // 用于标记列
int main()
{
int n , m ;
while (scanf("%d%d" , &n , &m) != EOF)
{
memset(visx , 0 , sizeof(visx)) ;
memset(visy , 0 , sizeof(visy)) ;
int i , j ;
char t ;
for(i = 0 ; i < n ; i ++)
{
for(j = 0 ; j < m ; j ++)
{
cin >> t ;
if(t == 'S')
{
visx[i] ++ ;
visy[j] ++ ;
}
}
}
int sumx = 0 ;
int sumy = 0 ;
for(i = 0 ; i < n ; i ++)
{
if(visx[i] > 0)
{
sumx ++ ;
}
}
for(i = 0 ; i < m ; i ++)
{
if(visy[i] > 0)
{
sumy ++ ;
}
}
int ans = n * m - sumx * sumy ;
printf("%d\n" , ans) ;
}
return 0 ;
}
B.Road Construction
题目大意：有n个城市，一开始，这些城市之间没有道路。让你在这些城市之间建造道路，同时满足一下条件：一、这些道路是双向的。
二、从一个城市能够到达其他任一个城市。三、一个城市到其他任意一个城市最多经过两条道路。 同时，有m对城市之间不能直接建造道路。请你设计一种方案使建造的道路总数最少。
解题思路：首先要明白这道题是建立一个连通图，n个顶点连通至少需要n—1条边。那么有没有可能只建造n—1条边就能满足上面的条件呢？答案是肯定的。只要找到一个点k，并且点k能够与所有的顶点之间建造公路就okay了。因为只需把所有的点（除k点外）与k点之间建造一条边就可以了，得出的图一定满足上面的条件。可能有人会问会不会找不到这样的k点呢？一定会！因为题目中指明了0 <= m < (n / 2) ， 可以推出 0 <= 2 * m < n
, 所以这样的k点一定存在。
下面请看代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std ;
int vis[1005] ;
int main()
{
int n , m ;
while (scanf("%d%d" , &n ,&m) != EOF)
{
memset(vis , 0 , sizeof(vis)) ;
int i ;
for(i = 0 ; i < m ; i ++)
{
int a , b ;
scanf("%d%d" , &a , &b) ;
vis[a] = 1 ;
vis[b] = 1 ;
}
int yuan ; // 即 点 k 的序号
for(i = 1 ; i <= n ; i ++)
{
if(vis[i] == 0)
{
yuan = i ;
break ;
}
}
printf("%d\n" , n - 1) ;
for(i = 1 ; i <= n ; i ++)
{
if(yuan != i)
{
printf("%d %d\n" , yuan , i) ;
}
}
}
return 0 ;
}
C.Purification
题目大意：给你一个n * n 的网格，行和列的标号都是从1到n 。网格上的符号有两种：“S”和“.”。你只能在符号为“.”的网格中放置咒语，这条咒语能够使它所在的行和列都清空。让你判定能否清空网格中的所有符号，如果能就输出最少的需要放置的咒语的数量，如果不能，就输出“-1”。
解题思路：如果能够清空网格中所有的符号，那么至少每一行需要放置一个咒语或者至少在每一列放置一个咒语，那么需要放置的最少的咒语的数量就是n。那么只要判断是否每一行都有“.”或者 每一列都有“.” 就可以了。代码如下：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std ;
const int MAXN = 1005 ;
int visx[MAXN] ;
int visy[MAXN] ;
int ansx[MAXN] ;
int ansy[MAXN] ;
char map[MAXN][MAXN] ;
int main()
{
int n ;
while (scanf("%d" , &n) != EOF)
{
memset(visx , 0 , sizeof(visx)) ;
memset(visy , 0 , sizeof(visy)) ;
int i , j;
for(i = 1 ; i <= n ; i ++)
{
for(j = 1 ; j <= n ; j ++)
{
cin >> map[i][j] ;
}
}
int cnt = 0 ;
for(i = 1 ; i <= n ; i ++)
{
for(j = 1 ; j <= n ; j ++)
{
if(map[i][j] == '.')
{
if(visx[i] == 0)
{
visx[i] = 1 ;
//visy[j] = 1;
ansx[cnt] = i ;
ansy[cnt] = j ;
cnt ++ ;
}
}
}
}
if(cnt == n)
{
for(i = 0 ; i < cnt ; i ++)
{
printf("%d %d\n" , ansx[i] , ansy[i]) ;
}
}
else
{
cnt = 0 ;
for(i = 1 ; i <= n ; i ++)
{
for(j = 1 ; j <= n ; j ++)
{
if(map[j][i] == '.')
{
if(visy[i] == 0)
{
visy[i] = 1 ;
//visy[j] = 1;
ansx[cnt] = j ;
ansy[cnt] = i ;
cnt ++ ;
}
}
}
}
if(cnt == n)
{
for(i = 0 ; i < cnt ; i ++)
{
printf("%d %d\n" , ansx[i] , ansy[i]) ;
}
}
else
printf("-1\n") ;
}
}
return 0 ;
}
D.Biridian Forest
题目大意：给你一个n * m 的矩形森林，有一个猎人要从逃脱次森林。在矩形森林的每个网格中共可能有以下几种符号：第一种：”T”，代表一棵树；第二种：“S”，代表猎人所在的位置。第三种：“E”，代表出口。第四种：“0” ~ “9” ， 代表这一网格中有几只怪物，他们尽量想办法和猎人战斗。规则：猎人每次可以往相邻的网格中移动一步，但是不能移动到有树的网格中；每个有怪物的网格，里面的所有怪物每次可以向相邻的网格中移动一步，但也不能移动到有树的网格中，同时，他们也可以原地不动。
当猎人和怪物处在同一个网格时，猎人会与怪物们战斗并杀死该网格中所有的怪物，请你求出猎人逃脱此森立最少需要杀死多少只怪物？（不要求猎人走的路程最短）
解题思路：此题看似比较难，其实只要动动脑筋想想就可以迎刃而解了。只要假设怪物们和猎人战斗的地点都在出口处就行了，这样只需算出猎人到达出口最少需要多少步，怪物们到达出口最少需要多少步，比猎人早到达出口或者和猎人一起到达出口的怪物一定会被猎人杀死，那些比猎人晚到达出口的怪物是没有机会和猎人战斗的。
注意：此题是有技巧的，如果从每个怪兽的位置bfs找出口的位置一定会TLE 的（笔者开始就是这样写的 ， 汗….），呵呵，其实逆向思维，只需从出口“E”的位置bfs找猎人和怪兽们的位置就可以了，这样只需进行一次bfs ！！！
请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std ;
const int MAXN = 1005 ;
int bu[MAXN * MAXN] ;
char map[MAXN][MAXN] ;
int X[4] = {0 , 0 , 1 , -1} ;
int Y[4] = {1 , -1 , 0 , 0} ;
int vis[MAXN][MAXN] ;
int n , m ;
int ren[MAXN * MAXN] ;
struct Node
{
int x ;
int y ;
int d ;
};
queue<Node> q ;
int cango(int x , int y)
{
if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && map[x][y] != 'T')
return 1 ;
return 0 ;
}
int cnt ;
void bfs(int i , int j)
{
while (!q.empty()) // 清空队列
{
q.pop() ;
}
Node start = {i , j , 0} ;
q.push(start) ;
Node temp ;
while (!q.empty())
{
temp = q.front() ;
vis[temp.x][temp.y] = 1 ;
q.pop() ;
int tx , ty ;
int k ;
for(k = 0 ; k < 4 ; k ++)
{
tx = temp.x + X[k] ;
ty = temp.y + Y[k] ;
if(cango(tx , ty))
{
vis[tx][ty] = 1 ;
Node tmp2 ;
tmp2.x = tx ;
tmp2.y = ty ;
tmp2.d = temp.d + 1 ;
if(map[tx][ty] >= '1' && map[tx][ty] <= '9')
{
bu[cnt] = tmp2.d ;
ren[cnt ++] = map[tx][ty] - '0' ;
}
else if(map[tx][ty] == 'S')
{
bu[0] = tmp2.d ;
}
q.push(tmp2) ;
}
}
}
}
int main()
{
while (scanf("%d%d" , &n , &m) != EOF)
{
int i , j ;
for(i = 0 ; i < n ; i ++)
{
scanf("%s" , map[i]) ;
}
cnt = 1 ; // 记录怪兽们的位置，注意cnt从1开始 ， cnt = 0 是记录猎人的位置的
for(i = 0 ; i < n ; i ++)
{
for(j = 0 ; j < m ; j ++)
{
if(map[i][j] == 'E')
{
memset(vis , 0 ,sizeof(vis)) ;
bfs(i , j) ;
break ;
}
}
}
if(cnt == 1)
{
printf("0\n") ;
}
else
{
int sum = 0 ;
int k ;
for(k = 1 ; k < cnt ; k ++)
{
if(bu[0] >= bu[k])
{
sum += ren[k] ;
}
}
printf("%d\n" , sum) ;
}
}
return 0 ;
}