/*
一次AC,题不难。
找错经历:
①处出错,不能使用sizeof()计算形参中数组长度
②G的状态应分三种情况讨论。
题意:一个棋盘,放置rook,要求不能在同一行或同一列,除非中间有墙。
思路:回溯+状态存储,G值为0表示有墙,为1表示可放,为-1表示有冲突。
*/
#include <cstdio>
#include <cstring>
int n;
int ans;
void dfs1(int (*G)[7],int x,int y)
{
G[x][y]=-1;//②
for(int i=x-1;i>=1;i--)
if(G[i][y])
G[i][y]=-1;
else
break;
for(int i=x+1;i<=n;i++)
if(G[i][y])
G[i][y]=-1;
else
break;
for(int i=y-1;i>=1;i--)
if(G[x][i])
G[x][i]=-1;
else
break;
for(int i=y+1;i<=n;i++)
if(G[x][i])
G[x][i]=-1;
else
break;
}
void dfs(int (*G)[7],int count)
{
int GG[7][7];
memcpy(GG,G,sizeof(GG));//不能使用形参中的数组①
bool ok=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(GG[i][j]==1)
{
//printf("%d %d\n",i,j);
ok=true;
dfs1(GG,i,j);
dfs(GG,count+1);
memcpy(GG,G,sizeof(GG));
}
}
if(!ok)
{
if(count>ans)
ans=count;
}
}
int main()
{
//freopen("data.in","r",stdin);
int G[7][7];
while(scanf("%d",&n) && n)
{
char c;
memset(G,0,sizeof(G));
for(int i=0;i<n;i++)
{
getchar();
for(int j=0;j<n;j++)
{
c=getchar();
if(c=='.')
G[i+1][j+1]=1;
}
}
ans=0;
dfs(G,0);
printf("%d\n",ans);
}
}
分享到:
相关推荐
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 高清 书签版
Apache You don't have permission to access / on this server是一个在配置Apache时候,常常遇到的问题
You Don t Know JS ES6 Beyond 2015
You Don't Know JS(中英全6本,带目录),You Don't Know JS(中英全6本,带目录)
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 ...
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 ...
You Don't Know JS(高清带目录中文版)1-3,单次上传不能超过60M,分两次上传了。4-6到要去另一个资源贴上下。。。
极好的经典 设计书籍,做UE/UI或者产品设计的必看经典书籍
Why don't you get her a scarfPPT教案学习.pptx
新目标英语八年级下册Unit8 What don’t you get her a scarf知精选.doc
当然,您也可以手动禁用所有选项,然后再次激活,但是使用“Don’t Sleep”功能可以节省很多手部动作,还可以节省时间!而且它比以往任何时候都容易。 Windows 电源管理工具 Don't Sleep 中文版 Windows 电源管理...
Like other books in this series, You Don’t Know JS: Types & Grammar dives into trickier parts of the language that many JavaScript programmers simply avoid or assume don’t exist (like types)....
Don’t Pay for What You Don’t Need Guide.pdf
陕西省榆林市定边县安边中学八年级英语下册 Unit 8 Why don’t you get her a scarf Period 5导学案(无答案) 人教新目标版