[kuangbin帶你飛]專題一 簡單搜尋

NO IMAGE

Links:https://vjudge.net/contest/146840#overview


A – 棋盤問題

比較簡單的搜尋題

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n, k, ans;
char map[10][10];
bool line[10];
void dfs(int lie, int num){
if (num == k){
ans  ;
return;
}
if (lie == n){
return;
}
dfs(lie   1, num);
for (int i = 0; i<n; i  ){
if (map[lie][i] == '#'&&line[i] == false){
line[i] = 1;
dfs(lie   1, num   1);
line[i] = 0;
}
}
}
int main(){
while (~scanf("%d%d", &n, &k), n != -1){
ans = 0;
memset(line, 0, sizeof(line));
for (int i = 0; i<n; i  ){
cin >> map[i];
}
dfs(0, 0);
printf("%d\n", ans);
}
return 0;
}

B – Dungeon Master

二維廣搜變成三維廣搜,沒什麼其他不同

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<queue>
using namespace std;
int l, r, c,ans;
int map[32][32][32];
bool v[32][32][32];
int dl[6] = { 0, 0, 0, 0, 1, -1 };
int dx[6] = { -1, 0, 0, 1, 0, 0 };
int dy[6] = { 0, -1, 1, 0, 0, 0 };
struct point{
int l;
int x;
int y;
int s;
}beg;
queue<point> que;
int bfs(){
int ans = -1;
while (!que.empty()){
point cnt = que.front();
que.pop();
if (map[cnt.l][cnt.x][cnt.y]=='E'){ ans = cnt.s; break; }
for (int i = 0; i < 6; i  ){
point np={ cnt.l   dl[i], cnt.x   dx[i], cnt.y   dy[i], cnt.s   1 };
if (np.l >= 0 && np.l<l&&np.x>=0 && np.x<r&&np.y>=0 && np.y < c){
if (map[np.l][np.x][np.y] != '#'&&v[np.l][np.x][np.y]==0){
que.push(np);
v[np.l][np.x][np.y] = 1;
}
}
}
}
while (!que.empty()){
que.pop();
}
return ans;
}
int main(){
while (scanf("%d%d%d", &l, &r, &c)){
memset(v, 0, sizeof(v));
getchar();
if (l == 0){ return 0; }
for (int i = 0; i < l; i  ){
for (int j = 0; j < r; j  ){
for (int k = 0; k < c; k  ){
map[i][j][k]=getchar();
if (map[i][j][k] == 'S'){
beg.l = i, beg.x = j, beg.y = k,beg.s=0;
v[i][j][k] = 1;
}
}
getchar();
}
getchar();
}
que.push(beg);
int ans = bfs();
if (ans == -1){
printf("Trapped!\n");
}
else{
printf("Escaped in %d minute(s).\n",ans);
}
}
return 0;
}

C – Catch That Cow

數軸上的bfs(),給定幾個移動,求最少步驟達到要求的位置。

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<queue>
using namespace std;
int fx, fy;
int v[300005];
struct point{
int x;
int s;
}beg;
queue<point> que;
int bfs(){
int ans = -1;
while (!que.empty()){
point cnt = que.front();
que.pop();
if (cnt.x == fy){
return cnt.s;
}
if (cnt.x   1 <= 100000&&v[cnt.x   1] == 0){
que.push({ cnt.x   1, cnt.s   1 });
v[cnt.x   1] = 1;
}
if (cnt.x - 1 >= 0 && v[cnt.x - 1] == 0){
que.push({ cnt.x - 1, cnt.s   1 });
v[cnt.x - 1] = 1;
}
if (cnt.x != 0 &&cnt.x*2<=300000&& v[cnt.x * 2] == 0){
que.push({ cnt.x * 2, cnt.s   1 });
v[cnt.x * 2] = 1;
}
}
return ans;
}
int main(){
scanf("%d%d", &fx, &fy);
beg.x = fx, beg.s = 0;
que.push(beg);
int astep=bfs();
printf("%d", astep);
return 0;
}

D – Fliptile

經典的翻牌子,列舉搜尋。

E – Find The Multiple

著給定數字的倍數中全為0.1的,一開始看位數最多為200認為dfs會超時,然後就用了廣搜,結果爆記憶體,最後打了表過的,其實答案用longlong就能存的下,深搜就能解決。

mle的廣搜程式碼

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int n;
struct kk{
bool ans[105];
int n;
int mod;
};
queue<kk> que;
kk bfs(){
kk ans;
while (~que.empty()){
kk cnt = que.front();
que.pop();
int cnt_mod = cnt.mod;
int cnt_n = cnt.n;
if (cnt_n > 101){ continue; }
cnt.ans[cnt_n] = 1;
int newmod = (cnt_mod * 10   1) % n;
if (newmod == 0){ ans = cnt; break; }
cnt.mod = newmod, cnt.n  = 1; que.push(cnt);
cnt.n--;
cnt.ans[cnt_n] = 0;
newmod = (cnt_mod*10) % n;
if (newmod == 0){ ans = cnt; break; }
cnt.mod = newmod,cnt.n =1; que.push(cnt);
}
while (!que.empty()){ que.pop(); }
return ans;
}
int main(){
while (~scanf("%d", &n), n != 0){
if (n == 1){ printf("1\n"); }
else if (n == 0){ printf("0\n"); }
else{
kk beg, ans;
beg.ans[0] = 1;
beg.mod = 1, beg.n = 1;
que.push(beg);
ans = bfs();
int k = ans.n;
for (int i = 0; i <= k; i  ){
printf("%d", ans.ans[i]);
}
printf("\n");
}
}
return 0;
}

F – Prime Path

很經典的搜尋題了。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
#include<fstream>
#include<math.h>
using namespace std;
int n,beg,en;
bool isprim[10000];
bool v[10000];
void is_prim(){
for (int i = 1000; i <= 9999; i  ){
bool r = true;
for (int j = 2; j < sqrt((double)i)   1; j  ){
if (i%j == 0){ r = false; break; }
}
if (r == true){ isprim[i] = true; }
}
}
struct N{
int step;
int num[4];
};
queue<N> que;
int getnum(int *n){
return n[0] * 1000   n[1] * 100   n[2] * 10   n[3];
}
int bfs(){
int ans = 0;
while (!que.empty()){
N cnt = que.front();
que.pop();
int cntnum = getnum(cnt.num);
//int cntnum = cnt.num[0] * 1000   cnt.num[1] * 100   cnt.num[2] * 10   cnt.num[3];
v[cntnum] = true;
if (cntnum == en){ ans = cnt.step; break; }
cnt.step  ;
for (int k = 0; k < 4; k  ){
int cc = cnt.num[k];
for (int i = 0; i < 10; i  ){
cnt.num[k] = i;
int newnum = getnum(cnt.num);
if (v[newnum] == 0 && isprim[newnum]){
que.push(cnt);
}
}
cnt.num[k] = cc;
}
}
while (!que.empty()){ que.pop(); }
return ans;
}
int main(){
is_prim();
int t;
scanf("%d", &t);
while (t--){
memset(v, 0, sizeof(v));
scanf("%d%d", &beg, &en);
N b;
for (int i = 3; i >=0; i--){
b.num[i] = beg % 10;
beg /= 10;
}
b.step = 0;
que.push(b);
int ans = bfs();
printf("%d\n", ans);
}
return 0;
}

G – Shuffle’m Up

模擬洗牌的搜尋題

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<fstream>
#include<set>
#include<math.h>
using namespace std;
string target;
int len;
set<string> s;
struct N{
string str;
int step;
};
queue<N> que;
string getstr(string a,string b){
string cnt = "";
for (int i = 0; i < len; i  ){
cnt.push_back(a[i]);
cnt.push_back(b[i]);
}
return cnt;
}
int bfs(){
int ans = -1;
while (!que.empty()){
N cnt = que.front();
que.pop();
string cntstr = cnt.str;
s.insert(cntstr);
if (cntstr == target){ ans = cnt.step; break; }
string a = cntstr.substr(0, len);
string b = cntstr.substr(len, 2 * len);
//string newa = getstr(a, b);
//if (!s.count(newa)){
//  s.insert(newa);
//  que.push({ newa, cnt.step   1 });
//}
string newb = getstr(b, a);
if (!s.count(newb)){
s.insert(newb);
que.push({ newb, cnt.step   1 });
}
}
while (!que.empty()){ que.pop(); }
return ans;
}
int main(){
int t;
string a, b;
scanf("%d", &t);
for(int k=1;k<=t;k  ){
s.clear();
scanf("%d", &len);
cin >> a >> b >> target;
N start = { a   b, 0 };
que.push(start);
int ans = bfs();
printf("%d %d\n", k, ans);
}
return 0;
}

H – Pots

兩個水杯倒水,給定幾個操作,要求最少步驟使一個杯子裡的水等於c,並且輸出步驟,這點比較煩,所以我在bfs佇列的結構體里加了一個string存步驟,就很方便了。純屬對程式碼,注意無法完成要輸出impossible。

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<string.h>
using namespace std;
int a, b, c;
bool v[105][105];
struct wa{
int l, r;
int step;
string str;
};
queue<wa> que;
wa bfs(){
wa ans = {0,0,-1,""};
while (!que.empty()){
wa cnt = que.front();
que.pop();
int step = cnt.step;
if (cnt.l == c || cnt.r == c){ return cnt; }
if (cnt.l > 0){//a倒水
wa newp = { 0, cnt.r, step   1, cnt.str };
newp.str.insert(newp.str.length(), "DROP(1)\n");
if (v[newp.l][newp.r] == 0){
v[newp.l][newp.r] = 1;
que.push(newp);
}
}
if (cnt.l<a){//a裝水
wa nnewp = { a, cnt.r, step   1, cnt.str };
nnewp.str.insert(nnewp.str.length(), "FILL(1)\n");
if (v[nnewp.l][nnewp.r] == 0){
v[nnewp.l][nnewp.r] = 1;
que.push(nnewp);
}
}
if (cnt.r<b){//a倒水b
wa nnewp = { cnt.l - b   cnt.r, b, step   1, cnt.str };
if (cnt.l<b - cnt.r){
nnewp.l = 0, nnewp.r = cnt.r   cnt.l;
}
nnewp.str.insert(nnewp.str.length(), "POUR(1,2)\n");
if (v[nnewp.l][nnewp.r] == 0){
v[nnewp.l][nnewp.r] = 1;
que.push(nnewp);
}
}
if (cnt.r >0){//b倒水
wa newp = { cnt.l, 0, step   1, cnt.str };
newp.str.insert(newp.str.length(), "DROP(2)\n");
if (v[newp.l][newp.r] == 0){
v[newp.l][newp.r] = 1;
que.push(newp);
}
}
if (cnt.r<b){//b裝水
wa nnewp = { cnt.l,b, step   1, cnt.str };
nnewp.str.insert(nnewp.str.length(), "FILL(2)\n");
if (v[nnewp.l][nnewp.r] == 0){
v[nnewp.l][nnewp.r] = 1;
que.push(nnewp);
}
}
if (cnt.l<a){//b倒水a
wa nnewp = {a, cnt.r-a cnt.l, step   1, cnt.str };
if (cnt.r<a - cnt.l){
nnewp.r = 0, nnewp.l = cnt.r   cnt.l;
}
nnewp.str.insert(nnewp.str.length(), "POUR(2,1)\n");
if (v[nnewp.l][nnewp.r] == 0){
v[nnewp.l][nnewp.r] = 1;
que.push(nnewp);
}
}
}
return ans;
}
int main(){
cin >> a >> b >> c;
wa beg = { 0, 0, 0, "" };
v[0][0] = 1;
que.push(beg);
wa ans=bfs();
if (ans.step == -1){
cout << "impossible\n";
}
else{
cout << ans.step << endl;
cout << ans.str;
}
return 0;
}

I – Fire Game

可以在兩個地方點火,問所有草地被燒著的最短時間,資料較小,列舉點就行,兩個點相同時只往佇列里加一個點。
oj炸了,不知道程式碼對不對

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<fstream>
#include<set>
#include<math.h>
using namespace std;
int N, M;
int total,cntnum;
char map[105][105];
bool v[105][105];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
struct sit{
int x,y;
int step;
};
queue<sit> que;
int bfs(){
int ans = 0x3f3f;
while (!que.empty()){
sit cnt = que.front();
que.pop();
cntnum  ;
if (cntnum == total){ ans = cnt.step; break; }
for (int i = 0; i < 4; i  ){
sit newp = { cnt.x   dx[i], cnt.y   dy[i], cnt.step   1 };
if (newp.x >= 0 && newp.x < N&&newp.y >= 0 && newp.y < M&&v[newp.x][newp.y] == 0&&map[newp.x][newp.y]=='#'){
v[newp.x][newp.y] = 1;
que.push(newp);
}
}
}
while (!que.empty()){ que.pop(); }
return ans;
}
int main(){
int t;
scanf("%d", &t);
for (int k = 1; k <= t; k  ){
scanf("%d%d",&N, &M);
for (int i = 0; i < N; i  ){
scanf("%s", map[i]);
}
total =cntnum= 0;
for (int i = 0; i < N; i  ){
for (int j = 0; j < M; j  ){
if (map[i][j] == '#'){ total  ; }
}
}
int ans = 0x3f3f;
for (int i = 0; i < N; i  ){
for (int j = 0; j < M; j  ){
for (int k = 0; k < N; k  ){
for (int l = 0; l < M; l  ){
if (map[i][j] == '#'&&map[k][l] == '#'){
cntnum = 0;
memset(v, 0, sizeof(v));
sit beg = { i, j, 0 };
v[i][j] = 1;
que.push(beg);
if (i != k||j != l){
sit beg1 = {k, l, 0};
que.push(beg1);
v[k][l] = 1;
}
ans = min(ans, bfs());
}
}
}
}
}
printf("Case %d: ", k);
if (ans == 0x3f3f){ printf("-1\n"); }
else{ printf("%d\n",ans); }
}
return 0;
}

J – Fire!

有人有火,著火的地方不能走,問逃出去的最少步驟。
注意清空佇列。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<set>
#include<math.h>
using namespace std;
int N, M;
char map[1005][1005];
bool fire[1005][1005];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
struct sit{
int x, y;
int step;
bool is_fire;
};
queue<sit> que;
int bfs(){
int ans = -1;
while (!que.empty()){
sit cnt = que.front();
que.pop();
for (int i = 0; i < 4; i  ){
sit newp = { cnt.x   dx[i], cnt.y   dy[i], cnt.step   1, cnt.is_fire };
if (newp.is_fire){
if (newp.x >= 0 && newp.x < N&&newp.y >= 0 && newp.y < M&&map[newp.x][newp.y] != '#'&&fire[newp.x][newp.y] == 0){
fire[newp.x][newp.y] = 1, que.push(newp);
}
}
else{
if (newp.x < 0 || newp.y < 0 || newp.x >= N || newp.y >= M){ ans = newp.step; return ans; }
else{
if (fire[newp.x][newp.y] == 0 && map[newp.x][newp.y] != '#'){
fire[newp.x][newp.y] = 1; que.push(newp);
}
}
}
}
}
return ans;
}
int main(){
int t;
scanf("%d", &t);
while (t--){
memset(fire, 0, sizeof(fire));
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i  ){
scanf("%s", map[i]);
}
sit p = { 0, 0, 0, 0 }, f = { 0, 0, 0, 1 };
for (int i = 0; i < N; i  ){
for (int j = 0; j < M; j  ){
if (map[i][j] == 'J'){ p.x = i, p.y = j; }
else if (map[i][j] == 'F'){ f.x = i, f.y = j; fire[f.x][f.y] = 1; que.push(f); }
}
}
fire[p.x][p.y] = 1;
que.push(p);
int ans = bfs();
while (!que.empty()){ que.pop(); }
if (ans == -1){ printf("IMPOSSIBLE\n"); }
else{ printf("%d\n", ans); }
}
return 0;
}

M – 非常可樂

經典模擬廣搜,

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<fstream>
#include<set>
#include<math.h>
using namespace std;
int S, N, M;
struct sit{
int a, b, c;
int step;
};
queue<sit> que;
bool v[101][101][101];
int bfs(){
int ans = -1;
while (!que.empty()){
sit cnt = que.front();
que.pop();
if ((cnt.a == S / 2 && cnt.b == S / 2) || (cnt.a == S / 2 && cnt.c == S / 2) || (cnt.b == S / 2 && cnt.c == S / 2)){ ans = cnt.step; break; }
if (cnt.a != 0){
sit newp = { cnt.a - N   cnt.b, N, cnt.c,cnt.step 1 }; if (v[newp.a][newp.b][newp.c] == 0){ v[newp.a][newp.b][newp.c] = 1; que.push(newp); } 
sit newp1 = { cnt.a - M   cnt.c, cnt.b, M, cnt.step   1 };
if (v[newp1.a][newp1.b][newp1.c] == 0){ v[newp1.a][newp1.b][newp1.c] = 1; que.push(newp1); }
}
if (cnt.b != 0){
sit newp = { cnt.a   cnt.b, 0, cnt.c, cnt.step   1 }; if (v[newp.a][newp.b][newp.c] == 0){ v[newp.a][newp.b][newp.c] = 1; que.push(newp); }
if (M - cnt.c >= cnt.b){ sit newp1 = { cnt.a, 0, cnt.c   cnt.b, cnt.step   1 }; if (v[newp1.a][newp1.b][newp1.c] == 0){ v[newp1.a][newp1.b][newp1.c] = 1; que.push(newp1); } }
else{ sit newp1 = { cnt.a, cnt.b - M   cnt.c, M, cnt.step   1 }; if (v[newp1.a][newp1.b][newp1.c] == 0){ v[newp1.a][newp1.b][newp1.c] = 1; que.push(newp1); } }
}
if (cnt.c != 0){
sit newp = { cnt.a   cnt.c, cnt.b, 0, cnt.step   1 }; if (v[newp.a][newp.b][newp.c] == 0){ v[newp.a][newp.b][newp.c] = 1; que.push(newp); }
if (N - cnt.b >= cnt.c){ sit newp1 = { cnt.a, cnt.b   cnt.c, 0, cnt.step   1 }; if (v[newp1.a][newp1.b][newp1.c] == 0){ v[newp1.a][newp1.b][newp1.c] = 1; que.push(newp1); } }
else{ sit newp1 = { cnt.a, N, cnt.c - N   cnt.b, cnt.step   1 }; if (v[newp1.a][newp1.b][newp1.c] == 0){ v[newp1.a][newp1.b][newp1.c] = 1; que.push(newp1); } }
}
}
while (!que.empty()){ que.pop(); }
return ans;
}
int main(){
while (~scanf("%d%d%d",&S, &N, &M),S!=0){
if (S % 2 != 0){ printf("NO\n"); }
else{
memset(v, 0, sizeof(v));
v[S][0][0] = 1;
sit beg = { S, 0, 0, 0 };
que.push(beg);
int ans = bfs();
if (ans != -1)
printf("%d\n", ans);
else printf("NO\n");
}
}
return 0;
}

N – Find a way

兩個到某一個相同麥當勞的時間和最小值,一開始對每一個麥當勞廣搜兩個人,然後超時了,然後改成兩個人搜尋麥當勞最短路徑,然後找最小和。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<fstream>
#include<set>
#include<math.h>
using namespace std;
int N, M;
struct point{
int x, y;
int step;
};
vector<point> ansa, ansb;
queue<point> que;
char map[205][205];
bool v[205][205];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };
void bfs(bool yyy){
while (!que.empty()){
point cnt = que.front();
que.pop();
if (map[cnt.x][cnt.y] == '@'){ if (yyy) ansa.push_back(cnt); else ansb.push_back(cnt); }
for (int i = 0; i < 4; i  ){
point newp = { cnt.x   dx[i], cnt.y   dy[i], cnt.step   1 };
if (newp.x >= 0 && newp.x < N&&newp.y >= 0 && newp.y < M&&map[newp.x][newp.y]!='#'&&v[newp.x][newp.y] == 0){
v[newp.x][newp.y] = 1;
que.push(newp);
}
}
}
}
int main(){
int ax, ay, bx, by;
while (~scanf("%d%d", &N, &M)){
ansa.clear(), ansb.clear();
for (int i = 0; i < N; i  ){
scanf("%s", &map[i]);
}
point a = { 0, 0, 0 }, b = {0,0,0};
for (int i = 0; i < N; i  ){
for (int j = 0; j < M; j  ){
if (map[i][j] == 'Y'){ a.x = i, a.y = j; }
else if (map[i][j] == 'M'){ b.x = i, b.y = j; }
}
}
memset(v, 0, sizeof(v));
que.push(a);
v[a.x][a.y] = 1;
bfs(1);
memset(v, 0, sizeof(v));
que.push(b);
v[b.x][b.y] = 1;
bfs(0);
int ans = 0x3f3f3f;
int len = ansa.size();
for (int i = 0; i < len; i  ){
for (int j = 0; j < len; j  ){
if (ansa[i].x == ansb[j].x&&ansa[i].y == ansb[j].y){
ans = min(ans, ansa[i].step   ansb[j].step);
}
}
}
printf("%d\n", ans * 11);
}
return 0;
}