首页 > 代码库 > uva639 暴力、回溯
uva639 暴力、回溯
题意：
在象棋中，“车”是可以在棋盘上沿着纵向或横向走任意格子的棋子。 在这个问题中，我们假设有一个4*4的小棋盘，
在这个棋盘上面包含着“墙”，而“车”是不能越过墙的。而我们的目标就是尽可能地放置更多地“车”到这个棋盘上去，使所有
的这些”车“互相不能吃到其它棋子。
在上面几副图中给出了几个样例， 棋盘上，格子全部是黑色的代表是“墙”， 黑色圆形的代表是“车”。
其中第二，三副图的棋子的放置是正确的，第四，五副图的棋子是错误的，因为那两个棋子可以互相吃到对方。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <map>10 #include <set>11 #include <algorithm>12 #include <iostream>13 using namespace std;14 int dir[5][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };15 char ch[10][10];16 int vis[10][10];17 int ans, n;18 19 inline bool judge( int x, int y )//从当前位置出发 判断改点所在的行列是否已经有车20 {21 for( int i = 0; i < 4; ++i )22 {23 int dx = x + dir[i][0];24 int dy = y + dir[i][1];25 while( dx < n && dx >= 0 && dy >= 0 && dy < n )26 {27 if( ch[dx][dy] == ‘X‘ )28 break;29 if( vis[dx][dy] )30 return true;31 dx += dir[i][0];32 dy += dir[i][1];33 }34 }35 return false;36 }37 38 void dfs( int x, int m )39 {40 for( int i = x; i < n; ++i )41 for( int j = 0; j < n; ++j )42 if( !vis[i][j] && ch[i][j] == ‘.‘ && !judge( i, j ) )43 {44 vis[i][j] = 1;45 dfs( i, m+1 );46 vis[i][j] = 0;47 }48 if( ans < m )49 ans = m;50 }51 52 int main()53 {54 while( ~scanf( "%d", &n ) && n )55 {56 for( int i = 0; i < n; ++i )57 scanf( "%s", ch[i] );58 memset( vis, 0, sizeof( vis ) );59 ans = 0;60 dfs( 0, 0 );61 printf( "%d\n", ans );62 }63 return 0;64 }
uva639 暴力、回溯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。