题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=580
最多16个格,2^16=65536可以枚举完,而且很多都是可以剪枝的,用dfs枚举就可以。
要注意的是如果在dfs之前用vis数组标记放下了“车”,那么要在dfs之后清除掉。
最多16个格,2^16=65536可以枚举完,而且很多都是可以剪枝的,用dfs枚举就可以。
要注意的是如果在dfs之前用vis数组标记放下了“车”,那么要在dfs之后清除掉。
#include<cstdio> #include<cstring> #define clear(x) (memset(x,0,sizeof(x))) char map[4][4]; bool vis[4][4]; int n,max; void getnext(int x,int y,int &nextx,int &nexty) { if(x<n-1) { nextx=x+1; nexty=y; } else if(y<n-1) { nextx=0; nexty=y+1; } else nextx=nexty=-1;//标志已经到最后了 } bool canputdown(int x,int y) { if(map[x][y]=='X') return 0; int i; for(i=x-1;i>=0&&map[i][y]=='.';i--) if(vis[i][y]) return 0; for(i=y-1;i>=0&&map[x][i]=='.';i--) if(vis[x][i]) return 0; return 1; } void dfs(int x,int y) { if(x==-1&&y==-1) { int cnt=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(vis[i][j]) cnt++; if(cnt>max) max=cnt; return; } int nextx,nexty; getnext(x,y,nextx,nexty); if(canputdown(x,y))//如果能放下 { vis[x][y]=1;//放 dfs(nextx,nexty); vis[x][y]=0;//不放 dfs(nextx,nexty); } else dfs(nextx,nexty); } int main() { //freopen("in.txt","r",stdin); int i; while(scanf("%d",&n)&&n) { for(i=0;i<n;i++) scanf("%s",map[i]); max=0; clear(vis); dfs(0,0); printf("%d\n",max); } return 0; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 903题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 724题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1642题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1051题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 875题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 696题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 660题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 764题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 606题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1127题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 879题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 659题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 875题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 790题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 827题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 746题目:http://uva.onlinejudge.org/i ...
相关推荐
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
PDF试题
UVA 499 Solution in C/ C++