In chess, the rook is a piece that can move any number of squares vertically or horizontally. In this problem we will consider small chess boards (at most 44)
that can also contain walls through which rooks cannot move. The goal is to place as many rooks on a board as possible so that no two can capture each other. A configuration of rooks islegalprovided that no two rooks are on the
same horizontal row or vertical column unless there is at least one wall separating them.
The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of rooks
in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.
Your task is to write a program that, given a description of a board, calculates the maximum number of rooks that can be placed on the board in a legal configuration.
The input file contains one or more board descriptions, followed by a line containing the number 0 that signals the end of the file. Each board description begins with a line containing a positive integernthat
is the size of the board;nwill be at most 4. The nextnlines
each describe one row of the board, with a `.' indicating an open space and an uppercase `X' indicating a wall. There are no spaces
in the input file.
For each test case, output one line containing the maximum number of rooks that can be placed on the board in a legal configuration.
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
5
1
5
2
4
Miguel A. Revilla
2000-01-17
和八皇后类似,使用回溯,只是判断是否冲突的方法不一样。
#include<iostream>
#include<cstring>
using namespace std;
char grid[6][6],vis[6][6];
int maxnum,n,num;
bool judge(int posx,int posy)
{
int i,j;
for(i=posx;i<n;i++)
{
if(vis[i][posy]==1&&grid[i][posy]=='.') return false;
else if(grid[i][posy]=='X') break;
}
for(i=posx;i>=0;i--)
{
if(vis[i][posy]==1&&grid[i][posy]=='.') return false;
else if(grid[i][posy]=='X') break;
}
for(i=posy;i<n;i++)
{
if(vis[posx][i]==1&&grid[posx][i]=='.') return false;
else if(grid[posx][i]=='X') break;
}
for(i=posy;i>=0;i--)
{
if(vis[posx][i]==1&&grid[posx][i]=='.') return false;
else if(grid[posx][i]=='X') break;
}
return true;
}
void search(int posx,int posy)
{
int i,j;
num++;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(judge(i,j)&&grid[i][j]=='.'&&vis[i][j]==0)
{
vis[i][j]=1;
search(i,j);
num--;
vis[i][j]=0;
}
}
}
if(num>maxnum) maxnum=num;
}
int main()
{
while(cin>>n&&n)
{
int i,j,k;
memset(grid,0,sizeof(grid));
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>grid[i][j];
maxnum=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(grid[i][j]!='X')
{
memset(vis, 0, sizeof(vis));
vis[i][j]=1;
num=0;
search(i,j);
vis[i][j]=0;
}
}
}
cout<<maxnum<<endl;
}
return 0;
}
分享到:
相关推荐
course don't load course don't load course don't load course don't load
Don’t Make Me Think田士庆
Don't Make Me Think.pdf 高清 书签版
Why don't you get her a scarfPPT教案学习.pptx
Apache You don't have permission to access / on this server是一个在配置Apache时候,常常遇到的问题
You Don t Know JS ES6 Beyond 2015
You probably don’t really know. Computers and the Internet have revolutionized the modern world, but if you’re like most people, you have no clue how these things work and don’t know the real ...
You Don't Know JS(中英全6本,带目录),You Don't Know JS(中英全6本,带目录)
极好的经典 设计书籍,做UE/UI或者产品设计的必看经典书籍
新目标英语八年级下册Unit8 What don’t you get her a scarf知精选.doc
No matter how much experience you have with JavaScript, odds are you don't fully understand the language. As part of the "You Don't Know JS" series, this concise yet in-depth guide focuses on new ...
don't try harder
You Don't Know JS(高清带目录中文版)1-3,单次上传不能超过60M,分两次上传了。4-6到要去另一个资源贴上下。。。
陕西省榆林市定边县安边中学八年级英语下册 Unit 8 Why don’t you get her a scarf Period 5导学案(无答案) 人教新目标版