网站：CSUST 8月1日
先总结下，不得不说死的很惨，又是第三就不说了，一共7道题，AC了5道，但是有一个组三个人是做的个人赛，有两人AK了.......Orz，然后深搜还是大问题，宽搜倒是不急了。
而且，其中还有一题是水过去的。唉，不说了，好好看。╮(╯▽╰)╭
A 骑士历遍问题：给出m,n，指大小为m*n的棋盘，问骑士是否能遍历整个棋盘，要求把路径打出来，（要按字典序）A Knight's Journey POJ 2488
网上找到了个很好地代码，解释很清晰：http://www.slyar.com/blog/poj-2488-c.html （以下解释来自这里）
Slyar:说一下题目大意。给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。
"马的遍历"是一道经典回溯题，当然还是DFS...这题有3个要密切注意的地方：
1、题目要求以"lexicographically"方式输出，也就是字典序...一开始没看懂这个词结果WA了N次...要以字典序输出路径，那么方向数组就要以特殊的顺序排列了...这样只要每次从dfs(1,1)开始搜索，第一个成功遍历的路径一定是以字典序排列...
2、国际象棋的棋盘，横行为字母，表示横行坐标的是y；纵行为数字，表示纵行的坐标是x...一开始又搞反了...
代码：16MS
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int map[][],x[],y[];
int d[][]={{-, -}, {-, }, {-, -}, {-, },{, -}, {, }, {, -}, {, }}; //字典序
int m,n,sign,step;
void dfs(int i,int j)
{
int a,b,k;
if(sign) //以历遍，跳出
return ;
step++;
x[step]=i; //当前位置
y[step]=j;
if(step==m*n) //步数=格子数
{
sign=;
return ;
}
map[i][j]=; //标记
for(k=;k<;k++)
{
b=j+d[k][]; //注意
a=i+d[k][];
if(map[a][b]== && a> && b> && a<=m && b<=n)
{
dfs(a,b);
step--; //不符合要求是回溯步数 }
}
map[i][j]=; //返回
}
int main()
{
int T,i,t=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
t++;
memset(map,,sizeof(map));
step=;
sign=;
dfs(,);
printf("Scenario #%d:\n", t);
if(sign)
{
for(i=;i<=m*n;i++)
printf("%c%d",y[i]+,x[i]); //注意这里，先是y，再是x
printf("\n\n"); //要空一行
}
else printf("impossible\n\n"); //要空一行
}
return ;
}
B 大意是：找出最大的湖泊的格子数，只能上下左右，对角不算相连 Avoid The Lakes POJ 3620
代码： 16ms BFS
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int d[][]={{,},{,},{,-},{-,}};
int map[][];
int m,n;
class A
{
public:
int a;
int b;
};
A q[];
void bfs()
{
A r,t;
int i,j,ans,k,maxn=;
for(j=;j<=m;j++) //扫描
for(k=;k<=n;k++)
{
if(map[j][k]==)
{
ans=;
int g=;
int h=;
map[j][k]=; //标记
q[g].a=j; //开始的位置
q[g].b=k;
g++;
while(h!=g)
{
r=q[h++];
for(i=;i<;i++)
{
t.a=r.a+d[i][];
t.b=r.b+d[i][];
if(t.a> && t.a<=m && t.b> && t.b<=n && map[t.a][t.b]==) //满足条件
{
q[g++]=t;
map[t.a][t.b]=; //标记
ans++;
}
}
}
if(maxn<ans) //找出最大值
maxn=ans;
}
}
cout<<maxn<<endl;
}
int main()
{
int i,j,k,x;
memset(map,,sizeof(map));
while(~scanf("%d%d%d",&m,&n,&x))
{
for(i=;i<x;i++)
{
scanf("%d%d",&j,&k);
map[j][k]=;
}
bfs();
}
return ;
}
另一种方法：DFS 16MS
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
int b[][]={{,},{-,},{,},{,-}};
int a[][];
int n,m,s;
void dfs(int i,int j)
{
int k,x,y;
s++;
a[i][j]=; //标记
for(k=;k<;k++)
{
x=i+b[k][];
y=j+b[k][] ;
if(x>&&x<=n&&y>&&y<=m&&a[x][y]==) //满足条件
dfs(x,y);
}
}
int main()
{
int t,a1,b1,i,j,MAX;
while(~scanf("%d%d%d",&n,&m,&t))
{
s=;
memset(a,,sizeof(a));
for(i=;i<t;i++)
{
scanf("%d %d",&a1,&b1);
a[a1][b1]=;
}
MAX=;
for(i=;i<=n;i++)
for(j=;j<=m;j++) // 遍历能够开始的点
if(a[i][j]==)
{
dfs(i,j);
if(s>MAX) //找到最大值
MAX=s;
s=;
}
printf("%d\n",MAX);
}
return ;
}
C 大意是：一个Z层x*y的楼房，要从起点到中点，问最少要走多少步？ 6个方向 Dungeon Master POJ 2251
代码： 0MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int number,Z,X,Y,x1,y1,z1,x2,y2,z2;
const int add[][]={{,,},{,-,},{,,},{-,,},{,,},{,,-}}; //上下左右前后6个方向
char a[][][];
class K
{
public:
int x,y,z,step;
}k[];
void bfs(int z,int x,int y)
{
int f=,r=,i,hx,hy,hz;
k[].x=x; //开始位置
k[].y=y;
k[].z=z;
k[].step=;
a[z][x][y]='#'; //标记
while(f<r)
{
for(i=;i<;i++)
{
hx=k[f].x+add[i][];
hy=k[f].y+add[i][];
hz=k[f].z+add[i][];
if(hx>= && hx<X && hy>= && hy<Y && hz>= && hz<Z && (a[hz][hx][hy]=='.' ||a[hz][hx][hy]=='E') )
{
if(a[hz][hx][hy]=='E')
{number=k[f].step+; return;}
k[r].x=hx;
k[r].y=hy;
k[r].z=hz;
k[r++].step=k[f].step+;
a[hz][hx][hy]='#';
}
}
f++;
}
return;
}
int main()
{
while(scanf("%d%d%d",&Z,&X,&Y)&&Z&&Y&&X)
{
int i,j,k;
memset(a,,sizeof(a));
for(i=;i<Z;i++) //输入地图
for(j=;j<X;j++)
scanf("%s",a[i][j]);
for(i=;i<Z;i++)
for(j=;j<X;j++)
for(k=;k<Y;k++)
if(a[i][j][k]=='S') //起点
{
x1=j;
y1=k;
z1=i;
}
number=;
bfs(z1,x1,y1);
if(number==)
printf("Trapped!\n");
else
printf("Escaped in %d minute(s).\n",number);
}
return ;
}
D 大意是：给出一个数m,要用n个数来凑，这n个数分别是a1,a2,a3a.....an.输出加法式 Sum It Up HDU 1258
代码： 15MS
#include<stdio.h>
2 int t,n,flag,a[],b[];
void dfs(int j,int k,int g)
{
int i;
if(j>t)
return ;
if(j==t) //凑成了t
{
flag=; //至少有一种凑的方法
for(i=;i<g-;i++)
printf("%d+",b[i]);
printf("%d\n",b[g-]); //打出等式
return ;
}
int last=-;
for(i=k;i<n;i++) //和每个排在自己之后的数加一次
{
if(j+a[i]>t) //超过就跳过
continue;
if(a[i]!=last) //不等于最后加的一个数，否则等式一样
22 {
last=b[g]=a[i]; //更新最后加的数
dfs(j+a[i],i+,g+);
}
}
}
int main()
{
int i;
while(~scanf("%d%d",&t,&n)&&n&&t)
{
flag=;
for(i=;i<n;i++)
scanf("%d",&a[i]);
printf("Sums of %d:\n",t);
dfs(, , );
if(flag)
printf("NONE\n");
}
}
另一份代码： 0ms
#include <stdio.h>
#include<string.h>
const int N=;
int a[N],n,t,flag;
bool vis[N];
void print()
{
flag=;
bool bol=;
int i;
for (i=;i<=n;i++)
if (vis[i]) //判断要不要加
{
if (bol) printf("+%d",a[i]);
else {bol=; printf("%d",a[i]);} //加的第一个数
}
printf("\n");
}
void dfs(int s,int p)
{
if (s==t) {print(); return;}
int i;
for (i=p+;i<=n;i++) //s和最后一个加数之后所有的数加一次
{
vis[i]=; //标记，代表加了这个数
if (s+a[i]<=t)
dfs(s+a[i],i);
vis[i]=; //不满足则退回到上一步
while (i<=n && a[i]==a[i+]) //一样的数不用再加,否则会重复
i++;
}
}
int main()
{
int i;
while (scanf("%d%d",&t,&n),n||t)
{
flag=;
for (i=;i<=n;i++)
scanf("%d",&a[i]);
printf("Sums of %d:\n",t);
dfs(,);
if (!flag) printf("NONE\n");
}
return ;
}
E大意是：在N*N的棋盘上放N个皇后，每两个皇后不能在同一行，同一列，也不能再同一斜线上（45°斜线），问有多少种方法？
这一道题我们是水过去的，因为规定了N<=10，所以只有10种情况，一一列举出来。╮(╯▽╰)╭
以下解释&&代码来自http://blog.sina.com.cn/s/blog_696187fd0100p5ri.html# （我修改了一些地方）
方法一： 递归回溯 //会超时......
#include<stdio.h>
#include<math.h>
#define N 15
int n; //皇后个数
int sum = ; //可行解个数
int x[N]; //皇后放置的列数
int place(int k)
{
int i;
for(i=;i<k;i++)
if(fabs(k-i)==fabs(x[k]-x[i]) || x[k] == x[i]) //fabs(k-i)==fabs(x[k]-x[i])是在同一斜线上，x[k] == x[i]在同一列
return ;
return ;
}
int queen(int t)
{
if(t>n) //当放置的皇后超过n时，可行解个数加1
sum++;
else
for(int i=;i<=n;i++)
{
x[t] = i; //标明第t个皇后放在第i列
if(place(t)) //如果可以放在某一位置，则继续放下一皇后
queen(t+);
}
return sum;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
sum=;
int t = queen();
printf("%d\n",t);
}
return ;
}
方法二：迭代回溯 可以理解但是....他是肿么想出来的.....其实和上面那个方法差不多，但是不是用递归实现的
#include<stdio.h>
#include<math.h>
#define N 15
int n;
int sum = ;
int x[N];
int place(int k) //判断能不能放这~~~
{
int i;
for(i=;i<k;i++)
if(fabs(k-i)==fabs(x[k]-x[i]) || x[k] == x[i]) //fabs(k-i)==fabs(x[k]-x[i])是在同一斜线上，x[k] == x[i]是在同一列上
return ;
return ;
}
int queen()
{
x[] = ;
int t=;
while(t>)
{
x[t]+=;
while(x[t]<=n && !place(t)) //一列列试，不行则放下一列
x[t]++;
if(x[t]<=n )
if(t==n)
sum++;
else
x[++t] = ;
else
t--; //满了则退回一步
}
return sum;
}
int main()
{
int t;
while(~scanf("%d",&n),n)
{
sum=;
t = queen();
printf("%d\n",t);
}
return ;
}
这样用记忆法才不会超时 15MS
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
int n,x[],sum,a[];
int place(int i)
{
for(int j=;j<i;j++)
if(fabs(i-j)==fabs(x[i]-x[j]) || x[i]==x[j])
return ;
return ;
}
int qeen(int i)
{
if(i>n)
sum++;
else
for(int j=;j<=n;j++)
{
x[i]=j;
if(place(i))
qeen(i+);
}
return sum;
}
int main()
{
for(n=;n<=;n++)
{
sum=;
a[n]=qeen();
}
while(~scanf("%d",&n)&&n)
printf("%d\n",a[n]);
return ;
}
E 大意是：找出棋盘上最多能放的棋子数，不能同一行同一列（隔开了就可以），允许在同一斜线上。
如图：
1：棋盘。2：正确的方法（也是最多的），3正确，4&5错误.
和N皇后有点像，指不过斜线也可以放，而且有墙，隔开也可以放。
代码： 来自：http://blog.****.net/hcbbt/article/details/9420387 15MS，头文件加上#include<iostream> using namespace std;之后时间为0MS
#include <cstdio>
const int maxn = ;
char map[maxn][maxn];
int ans, n;
bool isok(int x, int y)
{
for (int i = x + ; i <= n && map[i][y] != 'X'; i++) //遇到'X'就不再搜了
if(map[i][y] == '')
return false;
for (int i = x - ; i >= && map[i][y] != 'X'; i--)
if(map[i][y] == '')
return false;
for (int i = y + ; i <= n && map[x][i] != 'X'; i++)
if (map[x][i] == '')
return false;
for (int i = y - ; i >= && map[x][i] != 'X'; i--)
if (map[x][i] == '')
return false;
return true;
}
void dfs(int x, int y, int p)
{
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
if (map[i][j] == '.' && isok(i, j))
{
map[i][j] = ''; //代表已经放了一颗棋子
dfs(i, j, p + );
map[i][j] = '.';
}
if (ans < p)
ans = p;
}
int main()
{
while (scanf("%d", &n) && n)
{
gets(map[]); //可改成用scanf("%s",map[i]+1);来输入
for (int i = ; i <= n; i++)
gets(map[i] + );
ans = ;
dfs(, , );
printf("%d\n", ans);
}
return ;
}
G:G和C几乎一模一样，就不解释了：
代码： 31MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int number,quan,N,x1,y1,z1,x2,y2,z2;
const int add[][]={{,,},{,-,},{,,},{-,,},{,,},{,,-}};
char a[][][];
class K
{
public:
int x,y,z,step;
}k[];
void bfs(int z,int x,int y)
{
int f=,r=,i,hx,hy,hz;
memset(k,,sizeof(k));
k[].x=x;
k[].y=y;
k[].z=z;
k[].step=;
a[z][x][y]='X';
while(f<r)
{
for(i=;i<;i++)
{
hx=k[f].x+add[i][];
hy=k[f].y+add[i][];
hz=k[f].z+add[i][]; if(hx>= && hx<N && hy>= && hy<N && hz>= && hz<N && a[hz][hx][hy]=='O')
{
if(hz==z2 && hx==x2 && hy==y2)
{number=k[f].step+; return;}
k[r].x=hx;
k[r].y=hy;
k[r].z=hz;
k[r++].step=k[f].step+;
a[hz][hx][hy]='X';
}
}
f++;
}
return;
} int main()
{
char w[],q[];
while(~scanf("%s",q))
{
scanf("%d",&N);
int i,j,k;
memset(a,,sizeof(a));
for(i=;i<N;i++)
{
for(j=;j<N;j++)
scanf("%s",a[i][j]);
}
scanf("%d%d%d",&z1,&x1,&y1);
scanf("%d%d%d",&z2,&x2,&y2);
scanf("%s",w);
quan=;
if(a[z2][x2][y2]=='O') quan++;
if(a[z2][x2][y2]=='X') {a[z2][x2][y2]='O';quan--;}
number=;
if(z1==z2 && x1==x2 && y1==y2) {printf("%d 0\n",quan);continue;}
bfs(z1,x1,y1);
if(number==)
printf("NO ROUTE\n");
else
printf("%d %d\n",number+quan,number);
}
return ;
}