A - 棋盤問題 (POJ 1321)
題意
在一個n*n的棋盤上放置k個棋子，棋子不能同行同列扛禽。求方法數(shù)锋边。
思路分析
DFS遞推。
搜索當(dāng)前行编曼，每找到一個棋盤位置就遞歸到下一行搜索豆巨。
當(dāng)前行搜索完畢之后就搜索下一行。
代碼
#include<cstdio>
using namespace std;
char map[8][8];
int n, k, cnt, now; // 記錄總方案數(shù)和當(dāng)前已經(jīng)放置的棋子數(shù)目掐场。
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)
題意
三維迷宮題往扔，與迷宮題唯一的區(qū)別就是多了向下這一個方向。
思路
BFS+隊列熊户。迷宮題正常思路萍膛。
用結(jié)構(gòu)體作為隊列元素，三維數(shù)組存儲地圖嚷堡。
找到起點蝗罗，入隊，遍歷前后左右上下移動蝌戒，分別入隊串塑。
用vis數(shù)組進行判重。
代碼
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int x, y, z;
int step;
};
int sx, sy, sz; // 儲存起始點坐標(biāo)
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'){ // 遇到終點結(jié)束
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)
題意
農(nóng)夫去找他的牛北苟。農(nóng)夫和牛在一直線上桩匪，農(nóng)夫可以對自己的坐標(biāo)加一減一或者坐標(biāo)乘二來移動。求最少步數(shù)友鼻。
思路
BFS+隊列傻昙。農(nóng)夫有三種移動，+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次腿准。根據(jù)二進制來將每一個格子是0還是1選出(i>>j)&1贺嫂。
根據(jù)第一行的情況往下推導(dǎo)出所有的情況滓鸠，上一行是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點的當(dāng)前狀態(tài)
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]; // 統(tǒng)計步數(shù)
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曲饱，成功返回步數(shù)
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以內(nèi)的數(shù)的一個乘數(shù)悠抹，要求這個乘數(shù)的每一位都是0或者1。
思路
我的做法是DFS枚舉扩淀。從1開始向后推楔敌，判斷是否是n的乘數(shù)，如果是就輸出驻谆，不是就繼續(xù)卵凑。用無符號64位整數(shù)可以存到第十九層遞歸。
代碼
#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之間的素數(shù)A旺韭、B氛谜。要求從A到B掏觉，每次只能換一個數(shù)字区端，并且換完數(shù)字之后需要依然是素數(shù)。
思路
BFS+隊列澳腹，最短路织盼。
先打1000-9999素數(shù)表。根據(jù)素數(shù)表BFS找最短路酱塔。
先將起點入隊沥邻。將隊首取出，取個十百千四位羊娃。通過循環(huán)遍歷每一位唐全，找到每一位的更換數(shù)字，入隊。直到找到終點邮利。
代碼
#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){ // 循環(huán)尋找相連的節(jié)點
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)
題意
給兩疊牌弥雹，洗牌，兩疊牌間隔一張相互插入延届，最下一張是第二疊最下剪勿，最上一張是第一疊最上。第二次洗牌取前一半為第一疊方庭，后一半為第二疊厕吉。找出是否能到達目標(biāo)情況，需要洗幾次牌械念。
思路
暴力枚舉头朱。模擬洗牌過程，若干次之后肯定會回到初始狀態(tài)龄减。如果回到初始就跳出髓窜。記錄洗牌次數(shù)。
當(dāng)時做的時候調(diào)了很久的string欺殿，果然還是不熟悉C++的問題寄纵。
string的下標(biāo)取用是引用。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)
題意
有兩個容器棍潘，要達到目標(biāo)水量恃鞋。
三種操作，裝滿亦歉，倒空恤浪，從一個倒到另一個。
求次數(shù)和操作路徑肴楷。
思路
BFS+數(shù)組模擬隊列水由。
容器只有兩個，操作也有限赛蔫，所以能達到的水量肯定是有限的砂客。
用數(shù)組模擬隊列進行操作。因為水杯容量上限只有100呵恢，所以數(shù)組開到10000應(yīng)該足夠了鞠值。
通過循環(huán)來遍歷六種情況。六個if會很繁瑣渗钉，所以用switch來簡化彤恶。用vis判重。結(jié)構(gòu)體中加上一個pre屬性來記錄路徑。
代碼
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int A, B, C;
int vis[105][105];
int step; // 最終步數(shù)
int flag; // success or not
struct node{
int k1, k2, op, step, pre; // 當(dāng)前狀態(tài)声离、操作歇竟、步數(shù)、前一步下標(biāo)
}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連通塊。
經(jīng)典的DFS題目弧关。如果直接暴力遞歸的話會TLE盅安，所以需要用vis數(shù)組判重一下。
總結(jié)歸納
刷了十道題世囊，記錄有八道題别瞭，還有一題連通塊DFS和一題迷宮BFS不記。
BFS
BFS主要是用隊列來儲存下一個狀態(tài)株憾，循環(huán)遍歷同一個節(jié)點所能夠到達的所有情況蝙寨。所有可以配合方向數(shù)組來進行尋找，用結(jié)構(gòu)體來儲存節(jié)點的狀態(tài)或者坐標(biāo)嗤瞎。
適用于尋找最短路墙歪。
DFS
DFS主要用遞歸來向下尋找單條路徑的情況。遍歷所有路徑贝奇。
