ZOJ1002 Fire Net
题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
题目大意：
假想有这么一个由 N*N 个方块组成的城市。每一方块上要么是可能通行的，要么是不可通行的。现在要求你在可通行的方块上设置碉堡，每座碉堡都可以向四面开火，并能打穿整个城除非遇上不可通行的墙，也就是说，在没有墙阻拦的同一条线上，最多只能放置一个碉堡。问题输入城市信息后，要求你输出最大的可放置的碉堡数目。
解题思路：
最初，我们设想城市里没有任何一座碉堡，然后从左上角开始寻找第一个可以放置碉堡的地方，当找到可以放置碉堡的空位后，我们标记这地点为碉堡，接着又从左上角开始寻找第一个可以放置碉堡的地方。设置一个变量来存最大的可放置数，如果寻找到了右下角。我们继续还原另一个操作。这个我也说不清楚，不好说，看代码吧，嘻嘻....
源代码：
#include <iostream>using namespace std;char map;int n,best;bool canPut(int y,int x){int i;if(map == '.'){for(i=x-1;i>=0;i--)//向左查看if(map=='O')return false;else if(map=='X')break;;for(i=x+1;i<n;i++)//向右查看if(map=='O')return false;else if(map=='X')break;for(i=y-1;i>=0;i--) //向上查看if(map=='O')return false;else if(map=='X')break;for(i=y+1;i<n;i++) //向下查看if(map=='O')return false;else if(map=='X')break;return true;}return false;}void dfs(int m){int i,j;for(i=0;i<n;i++){for(j=0;j<n;j++){if(canPut(i,j)){//测试是否可以放置碉堡map='O'; //标记为碉堡dfs(m+1);map='.'; //还原，寻找另一个可放置的位置}}}best = m>best?m:best;}int main (){while(cin>>n,n!=0){ //读取城市地图信息for(int i=0;i<n;i++){for(int j=0;j<n;j++){switch(cin.get()){case '.': map = '.';continue;case 'X': map = 'X';continue;}j--;}}best = 0;dfs(0);cout<<best<<endl;}return 0;}
Run Time(ms) Run Memory(KB)
0 188
页:
[1]