A - 棋盘问题 (POJ 1321)
题意
在一个n*n的棋盘上放置k个棋子，棋子不能同行同列。求方法数。
思路分析
DFS递推。
搜索当前行，每找到一个棋盘位置就递归到下一行搜索。
当前行搜索完毕之后就搜索下一行。
代码
#include<cstdio>
using namespace std;
char map[8][8];
int n, k, cnt, now; // 记录总方案数和当前已经放置的棋子数目。
int vis[8]={0};
void dfs(int cur){
if(k == now){ cnt++; return; }
if(cur >= n) return;
for(int i=0; i<n; i++)
if(!vis[i] && map[cur][i]=='#'){
vis[i] = 1;
now++;
dfs(cur+1);
now--;
vis[i] = 0;
}
dfs(cur+1);
}
int main(){
while(scanf("%d%d", &n, &k) && n != -1 && k != -1){
for(int i=0; i<n; ++i)
scanf("%s", map[i]);
dfs(0);
printf("%d\n", cnt);
}
return 0;
}
B - Dungeon Master (POJ 2251)
题意
三维迷宫题，与迷宫题唯一的区别就是多了向下这一个方向。
思路
BFS+队列。迷宫题正常思路。
用结构体作为队列元素，三维数组存储地图。
找到起点，入队，遍历前后左右上下移动，分别入队。
用vis数组进行判重。
代码
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int x, y, z;
int step;
};
int sx, sy, sz; // 储存起始点坐标
int to[6][3]{1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1}; // 移动方向
int L, R, C; // 长宽高
char map[30][30][30];
int cnt, vis[30][30][30];
int check(int x, int y, int z){ // check it is illegal or not
if( x<0 || x>=L || y<0 || y>=R || z<0 || z>=C ) return 1;
if(vis[x][y][z] || map[x][y][z] == '#') return 1;
return 0;
}
void bfs(){
queue<node> q;
node a, b;
a.x = sx, a.y = sy, a.z = sz;
a.step = 0;
vis[a.x][a.y][a.z] = 1;
q.push(a);
while(!q.empty()){
a = q.front(); q.pop();
if(map[a.x][a.y][a.z] == 'E'){ // 遇到终点结束
cnt = a.step;
return;
}
for(int i=0; i<6; i++){ // 前后左右上下移动
b = a;
b.x += to[i][0];
b.y += to[i][1];
b.z += to[i][2];
if(check(b.x, b.y, b.z)) continue;
b.step = a.step + 1;
vis[b.x][b.y][b.z] = 1;
q.push(b);
}
}
cnt = -1;
}
int main(){
while(scanf("%d%d%d", &L, &R, &C), L){
for(int i=0; i<L; i++)
for(int j=0; j<R; j++)
scanf("%s", map[i][j]); // input
for(int i=0; i<L; i++)
for(int j=0; j<R; j++)
for(int k=0; k<C; k++)
if(map[i][j][k] == 'S'){
sx = i; sy = j; sz = k; // find start
}
memset(vis, 0, sizeof(vis)); // initial
bfs();
if(cnt == -1) { printf("Trapped!\n"); } // output
else printf("Escaped in %d minute(s).\n", cnt);
}
return 0;
}
C - Catch The Cow (POJ 3278)
题意
农夫去找他的牛。农夫和牛在一直线上，农夫可以对自己的坐标加一减一或者坐标乘二来移动。求最少步数。
思路
BFS+队列。农夫有三种移动，+1、-1、*2。
遍历这三种移动，入队。vis判重。
代码
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int n, k;
int Max, dis, Next;
int vis[MAXN], step[MAXN];
int ans;
int min(int n, int m){ return n<m? n:m; }
int bfs(){
queue<int> q;
q.push(n);
step[n] = 0;
vis[n] = 1;
while(!q.empty()){
dis = q.front(); q.pop();
for(int i=0; i<3; i++){ // 遍历三种移动方式
if(i == 0) Next = dis-1; // -1
else if(i == 1) Next = dis*2; // *2
else Next = dis+1; // +1
if(!vis[Next] && Next <= MAXN && Next >= 1){
q.push(Next);
step[Next] = step[dis]+1;
vis[Next] = 1;
}
if(Next == k) return step[Next];
}
}
return -1;
}
int main(){
scanf("%d%d", &n, &k); // input
memset(step, 0x3f, sizeof(step));
if(n>=k) printf("%d\n", n-k);
else printf("%d\n", bfs());
return 0;
}
D - Filptile (POJ 3279)
题意
黑白棋。翻一个自己和四周都换颜色。用0/1表示。
要求最终全为0。
思路
看不出来这是搜索题啊。明明是暴力枚举。
暴力枚举第一行的所有情况。因为一行有n列，所以共有1<<n种可能。所以遍历1<<n次。根据二进制来将每一个格子是0还是1选出(i>>j)&1。
根据第一行的情况往下推导出所有的情况，上一行是1的话那下一行就必须要翻。然后检查一下最后一行是否满足条件。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int dirc[5][2]{0, 0, 1, 0, -1, 0, 0, -1, 0, 1};
int m, n;
int map[15][15], filp[15][15], fin[15][15];
int getn(int x, int y){ // 获取x,y点的当前状态
int block = map[x][y];
for(int i=0; i<5; i++){
int bx = x+dirc[i][0];
int by = y+dirc[i][1];
if (bx>=0 && bx<m && by>=0 && by<n)
block += filp[bx][by];
}
return block&1;
}
int solve(){
for(int i=1; i<m; i++)
for(int j=0; j<n; j++)
if(getn(i-1, j)) filp[i][j]++;
for(int i=0; i<n; i++) // 判断最后一行是否符合要求
if(getn(m-1, i)) return 0;
int c = 0;
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
c += filp[i][j]; // 统计步数
return c;
}
int main(){
while (scanf("%d%d", &m, &n) != EOF) {
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
scanf("%d", &map[i][j]);
int cnt = INF;
for(int i=0; i<(1<<n); i++){
memset(filp, 0, sizeof(filp));
for(int j=0; j<n; j++) filp[0][j] = (i>>j)&1; // 二进制法暴力枚举第一行的所有情况。
int ans = solve(); // 计算第二行及之后的，如果失败返回0，成功返回步数
if(ans && ans < cnt) {
cnt = ans;
memcpy(fin, filp, sizeof(filp));
}
}
// 输出
if (cnt == INF) printf("IMPOSSIBLE\n");
else
for(int i=0; i<m; i++){
printf("%d", fin[i][0]);
for(int j=1; j<n; j++) printf(" %d", fin[i][j]);
printf("\n");
}
}
return 0;
}
E - Find The Multiple (POJ 1426)
题意
找到一个200以内的数的一个乘数，要求这个乘数的每一位都是0或者1。
思路
我的做法是DFS枚举。从1开始向后推，判断是否是n的乘数，如果是就输出，不是就继续。用无符号64位整数可以存到第十九层递归。
代码
#include<cstdio>
using namespace std;
bool find;
void dfs(unsigned __int64 t, int n, int step){
if (find) return;
if (!t%n){
printf("%I64u\n", t);
find = true;
return;
}
if (step==19) return; // 如果到了第19层就跳出
dfs(t*10, n, step+1);
dfs(t*10+1, n, step+1);
return;
}
int main(){
int n;
while(scanf("%d", &n), n){
find = false;
dfs(1, n, 0);
}
return 0;
}
F -Prime Path (POJ 3126)
题意
给出两个1000-9999之间的素数A、B。要求从A到B，每次只能换一个数字，并且换完数字之后需要依然是素数。
思路
BFS+队列，最短路。
先打1000-9999素数表。根据素数表BFS找最短路。
先将起点入队。将队首取出，取个十百千四位。通过循环遍历每一位，找到每一位的更换数字，入队。直到找到终点。
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int primeNum[10000];
int T, S, E;
int vis[10000], dis[10000];
int check[4];
void init(){
memset(primeNum, -1, sizeof(primeNum));
for(int i=1000; i<9999; i++){ // 打表
for(int j=2; j<i; j++)
if(!i%j){ primeNum[i] = 0; break; }
if(primeNum[i] != 0) { primeNum[i] = 1; }
}
scanf("%d",&T);
}
int bfs(){
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
int a;
queue<int> q;
q.push(S);
vis[S] = 1;
while (!q.empty()) {
a = q.front(); q.pop();
check[0] = a%10; // 个
check[1] = a%100/10; // 十
check[2] = a%1000/100; // 百
check[3] = a/1000; // 千
for(int i=0; i<4; i++){
int val = check[i]; // 暂时储存
for(int j=0; j<10; j++)
if(j != val){ // 循环寻找相连的节点
check[i] = j;
int xx = check[0] + check[1]*10 + check[2]*100 + check[3]*1000;
if(!vis[xx] && primeNum[xx]){ // 找到了
dis[xx] = dis[a]+1;
vis[xx] = 1;
if(xx == E) return dis[xx]; // 是终点
q.push(xx);
}
}
check[i] = val; // 还原
}
}
return -1;
}
int main(){
init();
while(T--){
scanf("%d%d", &S, &E);
int steps = bfs();
if(steps != -1) printf("%d\n", steps);
else printf("Impossible!\n");
}
return 0;
}
G - Shuffle'm Up (POJ 3087)
题意
给两叠牌，洗牌，两叠牌间隔一张相互插入，最下一张是第二叠最下，最上一张是第一叠最上。第二次洗牌取前一半为第一叠，后一半为第二叠。找出是否能到达目标情况，需要洗几次牌。
思路
暴力枚举。模拟洗牌过程，若干次之后肯定会回到初始状态。如果回到初始就跳出。记录洗牌次数。
当时做的时候调了很久的string，果然还是不熟悉C++的问题。
string的下标取用是引用。string只能通过C++的iostream来输入输出。
string在未赋值的时候不具有长度。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
string start, target;
char Begin[205];
int n;// the length of one stack
string Shuffle(string s){
string temp = start;
for(int i=0; i<n*2; i++){
if(~(i&1)) temp[i] = s[n+i/2];
if(i&1) temp[i] = s[i/2];
}
return temp;
}
int solve(){
string temp;
int cnt = 1;
temp = Shuffle(start);
while (1) {
if(temp == target) return cnt; // 如果成功，则返回答案
if(temp == start) return -1; // 如果和起始一样则不可能
temp = Shuffle(temp); cnt++; // 洗牌
}
}
int main(){
int T, time = 0;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
scanf("%s", Begin);
scanf("%s", Begin+n);
start = Begin;
cin >> target;
printf("%d ", ++time);
printf("%d\n", solve());
}
return 0;
}
H - Pots (POJ 3414)
题意
有两个容器，要达到目标水量。
三种操作，装满，倒空，从一个倒到另一个。
求次数和操作路径。
思路
BFS+数组模拟队列。
容器只有两个，操作也有限，所以能达到的水量肯定是有限的。
用数组模拟队列进行操作。因为水杯容量上限只有100，所以数组开到10000应该足够了。
通过循环来遍历六种情况。六个if会很繁琐，所以用switch来简化。用vis判重。结构体中加上一个pre属性来记录路径。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int A, B, C;
int vis[105][105];
int step; // 最终步数
int flag; // success or not
struct node{
int k1, k2, op, step, pre; // 当前状态、操作、步数、前一步下标
}q[105*105]; // 模拟队列
int op[105*105]; // 操作在队列中的编号
int lastOp; // 最终操作编号
void bfs(){
node now, next; int head, tail;
head = tail = 0;
q[tail].k1 = q[tail].k2 = q[tail].op = q[tail].step = q[tail].pre = 0;
tail++;
memset(vis, 0, sizeof(vis));
vis[0][0] = 1;
while(head < tail){
now = q[head]; head++; // 取队首，出队
if(now.k1 == C || now.k2 == C){
flag = 1;
step = now.step;
lastOp = head-1;
}
for(int i=1; i<=6; i++){
switch (i) {
case 1: next.k1 = A; next.k2 = now.k2; break;
case 2: next.k1 = now.k1; next.k2 = B; break;
case 3: next.k1 = 0; next.k2 = now.k2; break;
case 4: next.k1 = now.k1; next.k2 = 0; break;
case 5:
if(now.k1+now.k2 > A){ next.k1 = A; next.k2 = now.k1+now.k2-A; }
else { next.k1 = now.k1+now.k2; next.k2 = 0; }
break;
case 6:
if(now.k1+now.k2 > B){ next.k2 = B; next.k1 = now.k1+now.k2-B; }
else { next.k2 = now.k1+now.k2; next.k1 = 0; }
break;
}
next.op = i;
if(!vis[next.k1][next.k2]){
vis[next.k1][next.k2] = 1;
next.step = now.step+1;
next.pre = head-1;
q[tail].k1 = next.k1; q[tail].k2 = next.k2;
q[tail].op = next.op; q[tail].step = next.step; q[tail].pre = next.pre;
tail++;
if(next.k1 == C || next.k2 == C){
flag = 1;
step = next.step;
lastOp = tail-1;
return;
}
}
}
}
}
int main(){
while(~scanf("%d%d%d", &A, &B, &C)){
flag = step = 0;
bfs();
if(flag){
printf("%d\n", step);
op[step] = lastOp;
for(int i=step-1; i>0; i--)
op[i] = q[op[i+1]].pre;
for(int j=1; j<=step; j++){
switch (q[op[j]].op) {
case 1: printf("FILL(1)\n"); break;
case 2: printf("FILL(2)\n"); break;
case 3: printf("DROP(1)\n"); break;
case 4: printf("DROP(2)\n"); break;
case 5: printf("POUR(2,1)\n"); break;
case 6: printf("POUR(1,2)\n"); break;
}
}
}
else printf("impossible\n");
}
return 0;
}
L - Oil Deposits (HDU 1241)
题意
找出一共有多少块八方向连通的油田。
思路
DFS连通块。
经典的DFS题目。如果直接暴力递归的话会TLE，所以需要用vis数组判重一下。
总结归纳
刷了十道题，记录有八道题，还有一题连通块DFS和一题迷宫BFS不记。
BFS
BFS主要是用队列来储存下一个状态，循环遍历同一个节点所能够到达的所有情况。所有可以配合方向数组来进行寻找，用结构体来储存节点的状态或者坐标。
适用于寻找最短路。
DFS
DFS主要用递归来向下寻找单条路径的情况。遍历所有路径。
