这是第一次全部做出来的依次练习了，有一些都是做过两遍了的，但是还是错了几回，更多时候我还是应该多注意下细节，就好像章爷笑我 的一样，像什么vis[]标记没清0，什么格式错误，还有什么题目没看清，还是的注意一下了。
地址：8.1搜索练习
Problem A POJ 2488
题目大意就是说帮你给你个P*Q的棋盘，让马一次全部走完，每个点只能走一次，而且要按照字典序输出（这句话最坑！！！）。
这道题做过了两三次了，却老是被那句“字典序输出”给坑死。第一次看到这道题的时候，看到他说的字典序还以为是要让起点最小（虽然现在明白任何一个点作为起点都是可以到达终点的，只要里面有一条路可以遍历完），然后高高兴兴的枚举了起点，心想好简单叽里呱啦就敲完了，测试样例！过了！提交！WA了！然后就回头看代码，检查实在是无力了，在网上一搜，发现别人只用0,0,做起点就过了，马上改了提交！！！还是WA！！心力憔悴的我无力了，有重新找别人的代码，看到别人代码原来还有一小段注释
“int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1}; /*注意此处的数组数据， 为了保证每次的探索都是 符合字典序的*/”
然后才慢慢明白什么叫字典序输出,其实就是要让每一步走的位置要是在能够遍历每个点的前提下，尽量让字典序小。大家可以慢慢体会下。
贴代码：180 KB 16 ms
#include <stdio.h>
#include <string.h>
int vis[][]; const int d[][] = {{-,-},{-,},{-,-},{-,},{,-},{,},{,-},{,}};
int m,n,num,ans[],IsFind; void dfs(int x,int y)
{
if(x< || x>=m || y< || y>=n || vis[x][y] || IsFind) return ;
vis[x][y] = ;
ans[num++] = x*n+y;
if(num == m*n){IsFind = ; return;}
for(int i=;i< && !IsFind;i++)
{
dfs(x+d[i][], y+d[i][]);
}
if(!IsFind)
{
num--;
vis[x][y]=;
}
} int main()
{
int Case,T=;
while(~scanf("%d", &Case))while(Case--)
{
memset(vis,,sizeof(vis));
scanf("%d%d", &n, &m);
IsFind = ;
num=;
dfs(,);
printf("Scenario #%d:\n", ++T);
if(!IsFind)printf("impossible");
else for(int i=;i<num;i++)
{
printf("%c%d", ans[i]/n+'A', ans[i]%n+);
}
printf("\n\n");
if(!Case)T=;
}
return ;
}
Problem B Avoid The Lakes
简单的DFS求最大相连块 392 KB 16 ms
#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX(a,b) ((a) > (b) ? (a) : (b))
using namespace std; const int d[][] = {{-,},{,},{,-},{,}};
int N,M,K;
int Map[][],vis[][]; int DFS(int x,int y)
{
if(x< || x>=N || y< || y>=M || vis[x][y] || Map[x][y])return ;
int area = ;
vis[x][y] = ;
for(int i=;i<;i++)
{
area += DFS(x+d[i][], y+d[i][]);
}
return area;
} int main()
{
while(~scanf("%d%d%d",&N,&M,&K))
{
memset(Map,,sizeof(Map));
memset(vis,,sizeof(vis));
int a,b;
for(int i=;i<K;i++)
{
scanf("%d%d", &a,&b);
Map[a-][b-] = ;
}
int ans = ;
for(int i=;i<N;i++)
{
for(int j=;j<M;j++)if(!vis[i][j] && !Map[i][j])
{
int temp = DFS(i,j);
ans = MAX(ans, temp);
}
}
printf("%d\n", ans);
}
return ;
}
Problem C Dungeon Master
只是将求最短距离从二维增加到三维而已，数组加一维便可以实现436 KB16 ms
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int Dir[][] = {{,,},{,,-},{,,},{,-,},{,,},{-,,}};
struct node
{
int x,y,z;
int step;
}Start;
char Map[][][];
int vis[][][];
int L,R,C; void readData()
{
memset(vis,,sizeof(vis));
int IsFind_S=;
for(int i=;i<L;i++)
{
for(int j=;j<R;j++)
{
scanf("%s",Map[i][j]);
for(int k=;k<C && !IsFind_S;k++) if(Map[i][j][k] == 'S')
{
Start.x = i;
Start.y = j;
Start.z = k;
vis[i][j][k] = ;
Start.step = ;
IsFind_S = ;
}
}
}
} int BFS()
{
queue<node>q;
q.push(Start);
while(!q.empty())
{
node u = q.front();
q.pop();
int x = u.x, y = u.y, z = u.z;
if(Map[x][y][z] == 'E')return u.step;
for(int i=;i<;i++)
{
int nx = x + Dir[i][], ny = y + Dir[i][], nz = z + Dir[i][];
if(nx>= && nx<L && ny>= && ny<R && nz>= && nz < C && Map[nx][ny][nz]!='#' && !vis[nx][ny][nz])
{
vis[nx][ny][nz] = ;
node v;
v.x = nx; v.y = ny; v.z = nz; v.step = u.step+;
q.push(v);
}
}
}
return ;
} int main()
{
while(scanf("%d%d%d%*c", &L, &R, &C) && (L||R||C))
{
readData();
int ans = BFS();
if(!ans)printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n",ans);
}
return ;
}
Problem D Sum It Up
题目意思就是说给一个T和N个数，让你求出所有的可以让N个数里面找出一些数使得他们的和为T，求所有情况
由于题目说了每给一个数，这个数就只能用一次，就是说帮你给20,20,20，那么你可以用1个，2个或者3个20，但是你只用第1个或者只用第2个这两种情况都是一样的。这样的话我们每次储存时候就不要重复的储存每个数，而是另外开一个数组保存每个不一样的数，在开一个数组保存每个数的次数。那么在DFS的时候就按照每个不同的数出现的次数，从max~0一直到他们的和为T，就打印数组
代码里还有注释：228 KB 0 ms
#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX(a,b) ((a) > (b) ? (a) : (b))
using namespace std; int ans[];
int N,T,IsFind;
int use[],num[],NumOfUse;//NumOdUse用来统计有多好个不同的数，Use放的是不同的数，num放的是每个不同的数出现的次数
int index,k;//index表示DFS到了use[index]，ans总共有k个数 void DFS(int sum)
{
if(sum > T)return ;//和已经大于目标值，不需要继续搜索下去了
if(sum == T)//找到了就打印出来
{
IsFind = ;//找到了
for(int i=;i<k;i++)//打印
{
printf("%d%c", ans[i], (i==k-)? '\n' : '+');
}
return ;
}
if(index == NumOfUse)return;//已经找到了最后一个，任然不满足，返回
for(int i=num[index];i>=;i--)//对于第num[index]，枚举他出现的次数
{
for(int j=;j<i;j++)ans[k+j] = use[index];//向ans里放入i个数
index+=;k+=i;
DFS(sum+use[index-]*i);
index-=;k-=i;
}
} int main()
{
while(~scanf("%d%d", &T,&N) && N)
{
memset(num,,sizeof(num));
memset(ans,,sizeof(ans));
memset(use,,sizeof(use));
scanf("%d", &use[]);
num[] = ;
NumOfUse = ;
int temp;
for(int i=;i<N;i++)
{
scanf("%d", &temp);
if(temp == use[NumOfUse-])num[NumOfUse-]++;//由于题目保证输入时非升序，所以直接与前一个比较，相同，次数加1
else {use[NumOfUse] = temp; num[NumOfUse]++;NumOfUse ++;}//不同，数的个数加1
}
IsFind = ;
printf("Sums of %d:\n",T);
DFS();
if(!IsFind)printf("NONE\n");
}
return ;
}
Problem E N皇后问题
第一次，直接用白书的方法，超时
#include <stdio.h>
#include <string.h>
int vis[][],ans,n; void dfs(int cur)
{
if(cur == n){ans++;return;}
for(int i=;i<n;i++)
{
if(!vis[][i] && !vis[][i+cur] && !vis[][cur-i+n])
{
vis[][i] = vis[][i+cur] = vis[][cur-i+n] = ;
dfs(cur+);
vis[][i] = vis[][i+cur] = vis[][cur-i+n] = ;
}
}
} int main()
{
while(~scanf("%d", &n) && n)
{
ans = ;
memset(vis,,sizeof(vis));
dfs();
printf("%d\n", ans);
}
return ;
}
第二次，听了章爷的说法，打表，没有写 if(!n)break;WA了
#include <stdio.h>
#include <string.h>
int ans[] = {,,,,,,,,,,};
int main()
{
int n;
while(~scanf("%d", &n))
{
printf("%d\n",ans[n]);
}
return ;
}
第三次，终于过了228 KB15 ms
#include <stdio.h>
#include <string.h>
int ans[] = {,,,,,,,,,,};
int main()
{
int n;
while(~scanf("%d", &n) && n)
{
printf("%d\n",ans[n]);
}
return ;
}
Problem F Basic
此题我没有加入太多想法，有思路就敲了，所以写得有些挫，代码效率也不高，基本思路就是枚举每个点是否放上一个棋子，共有2^16种情况，然后就没放上一个就标记之后不能放上的点，找出者2^16中情况中可以放得数目最多的
其实也可以直接枚举每个点，放或者不放两种情况，搜索下一个点
代码 172 KB63 ms
#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX(a,b) ((a) > (b) ? (a) : (b))
using namespace std; int N;
char Map[][],vis[][];
const int d[][] = {{-,},{,},{,-},{,}}; int main()
{
while(~scanf("%d", &N) && N)
{
for(int i=;i<N;i++)
{
scanf("%s", Map[i]);
}
int Max = ;
for(int state = ;state < (<<(N*N));state++)
{
memset(vis,,sizeof(vis));
int ans = ;
for(int i=;i<(N*N);i++)
{
if(((<<i) & state) && Map[i/N][i%N]!='X' && !vis[i/N][i%N])
{
ans++;
vis[i/N][i%N] = ;
for(int k=;k<;k++)
{
int x = i/N +d[k][], y = i%N+d[k][];
while(x>= && x<N && y>= && y<N && Map[x][y]!='X')
{
vis[x][y] = ;
x+=d[k][]; y += d[k][];
}
}
}
}
Max = MAX(Max, ans);
}
printf("%d\n", Max);
}
return ;
}
Problem GAsteroids!
简单的三维BFS问题
#include <stdio.h>
#include <string.h>
#include <queue>
#define Is(a,b) (a>=0 && a<b)
#define MAX(a,b) ((a) > (b) ? (a) : (b))
using namespace std; const int Dir[][] = {{,,},{-,,},{,,},{,-,},{,,},{,,-}};
int vis[][][],N;
struct node{int x,y,z,step;};
node Start,End;
char Map[][][]; int ReadData()
{
memset(Map, , sizeof(Map));
char str[]={};
scanf("%s %d%*c", str, &N);
for(int i=;i<N;i++)
{
for(int j=;j<N;j++)
{
scanf("%s", Map[i][j]);
}
}
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
Start.x = z; Start.y = y; Start.z = x;
scanf("%d%d%d",&x,&y,&z);
End.x = z; End.y = y; End.z = x;
scanf("%s",str);
if(str[] == 'E')return ;
return ;
} int BFS()
{
memset(vis, , sizeof(vis));
queue<node>q;
Start.step = ;
q.push(Start);
node u, v;
vis[Start.x][Start.y][Start.z] = ;
while(!q.empty())
{
u = q.front();
q.pop();
int x = u.x, y = u.y, z = u.z;
if(x == End.x && y == End.y && z == End.z)return u.step;
for(int i=;i<;i++)
{
int nx = x+Dir[i][], ny = y+Dir[i][], nz = z+Dir[i][];
if(Is(nx,N) && Is(ny,N) && Is(nz, N) && !vis[nx][ny][nz] && Map[nx][ny][nz]!='X')
{
vis[nx][ny][nz] = ;
v.x = nx; v.y = ny; v.z = nz;
v.step = u.step+;
q.push(v);
}
}
}
return -;
} int main()
{
while(ReadData())
{
int ans = BFS();
if(ans == -)printf("NO ROUTE\n");
else printf("%d %d\n",N,ans);
}
}