[acm 1002] 浙大 Fire Net
已转战浙大
题目 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2
浙大acm 1002
#include <iostream> #include <cstdlib> #include <cmath> #include <list> #define OPEN 1 #define CASTLE 2 #define BLOCK 3 #define WALL 4 // summary: 用贪心原理找到一个影响地图最小的城堡的位置 // param in: map[] 输入的地图. n 地图大小. // param out: min_x,min_y 得出的放置的城堡的x,y坐标 // return: true 找到了合适的位置. false 没有可以放置城堡的地方了 #define MAX_POINT 10000 // 哨兵数 bool FindMinInfluencePosition(int map[][4], int n, int &min_x, int &min_y) { int min_point = MAX_POINT; // 赋哨兵值 min_x = min_y = 0; for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { if ( map[y][x] == OPEN) { int curr_point = 1; // 向上 for (int j = y - 1; j >= 0 && map[j][x] != WALL; j--) { if ( map[j][x] == OPEN) curr_point++; } // 向下 for (int j = y + 1; j < n && map[j][x] != WALL; j++) { if ( map[j][x] == OPEN) curr_point++; } // 向左 for (int j = x - 1; j >= 0 && map[y][j] != WALL; j--) { if ( map[y][j] == OPEN) curr_point++; } // 向右 for (int j = x + 1; j < n && map[y][j] != WALL; j++) { if ( map[y][j] == OPEN) curr_point++; } if (curr_point < min_point) { min_point = curr_point; min_x = x; min_y = y; } } } } // 检测是否放置了城堡 if (min_point != MAX_POINT) return true; else return false; } // summary: 根据位置放置城堡,在地图上标记出来 // param in: map[] 输入的地图. n 地图大小. x, y 放置的城堡的位置 void PlaceCastle(int map[][4], int n, int x, int y) { map[y][x] = CASTLE; // 向上 for (int j = y - 1; j >= 0 && map[j][x] != WALL; j--) { map[j][x] = BLOCK; } // 向下 for (int j = y + 1; j < n && map[j][x] != WALL; j++) { map[j][x] = BLOCK; } // 向左 for (int j = x - 1; j >= 0 && map[y][j] != WALL; j--) { map[y][j] = BLOCK; } // 向右 for (int j = x + 1; j < n && map[y][j] != WALL; j++) { map[y][j] = BLOCK; } } int main () { int map[4][4]; std::list<int> answer; int n; char c; // 读取数据 std::cin>>n; while (n != 0) { // 读取地图数据 for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { std::cin>>c; if (c == ‘.‘) map[y][x] = OPEN; else map[y][x] = WALL; } } // 处理地图 int castle_number = 0; int min_x, min_y; while (FindMinInfluencePosition(map, n, min_x, min_y) == true ) { castle_number++; PlaceCastle(map, n, min_x, min_y); } // 记录数据 answer.push_back(castle_number); // 输入下一个数 std::cin>>n; } // 输出数目 for (std::list<int>::iterator it=answer.begin() ; it != answer.end(); ++it) std::cout <<*it<<"\n"; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。