dfs题大杂烩
棋盘问题 POJ - 1321
和经典的八皇后问题一样. 给你一个棋盘,只有#区域可以放棋子,同时同一行和同一列只能有一个棋子. 问你放k个棋子有多少种方案.
很明显,这是搜索题.
因为每一行和每一列只能有一个棋子,所以我们可以从第k行一直到第n行枚举所有放棋子的情况,即我们从当前状态(当前行)dfs到第n行.然后符合添加的,我们就ans++.
dfs过程见代码.
#include <cstdio>
#include <cstring> int n,k,c,way; // 检查当前棋盘区域是否可以放置棋子
bool isok(char vis[][],int x,int y)
{
int i;
for(i=; i<n; ++i)
if('V'==vis[x][i])
return false;
for(i=; i<n; ++i)
if('V'==vis[i][y])
return false;
return true;
} void dfs(char vis[][],int cnt,int line)
{
int i,j;
char mvis[][]; if(k==cnt){
c++; // 走到了末尾 方案加一
return ;
}else if(line==n){
return ;
}else if(n-line+cnt<k){ //"剪枝"
return ;
}else{
memcpy(mvis,vis,sizeof(mvis)); //注意sizeof的"陷阱",sizeof(指针)==4,所以不能传sizeof(vis) sizeof(数组名)==数组大小
for(i=line; i<n; ++i){ //注意i=line 而不是0
for(j=; j<n; ++j){
if('#'==mvis[i][j] && isok(mvis,i,j)){ // 当前坐标是棋盘区域, 同时同一行同一列没有放置棋子
mvis[i][j] = 'V'; // 放棋子
dfs(mvis,cnt+,i+);
mvis[i][j] = '#'; // 取消放棋子的状态, 继续枚举其他情况
}
}
}
return ;
} } int main()
{
int i,j;
char map[][]; // freopen("D:\\input.txt","r",stdin);
while(scanf("%d%d",&n,&k) && (n!=- || k!=-)){
for(i=; i<n; ++i){
scanf("%s",map[i]);
}
c=;
dfs(map,,);
printf("%d\n",c);
}
return ;
}
Fliptile POJ - 3279
给你一个0和1组成的矩阵.你可以将某一格子阵翻转.但是你翻转一个格子,他上下左右的格子也会背翻转.
问你最后是否可以全部翻转成0
如果可以输出一个矩阵: 对应01矩阵翻转的次数.要求该答案矩阵的翻转次数最少,同时如果有多个解,输出字典序最小的一个.
如果不可以, 则输出IMPOSSIBLE
首先,我们分析一下, 我们发现,对于一个格子来说,翻转偶数次是没有意义的.翻转奇数次,才会改变状态.
因为对于一个格子,翻转偶数次是没有贡献的,翻转多个奇数次都等价于翻转一次,所以如果格子需要翻转,那么我们翻转一次就够了.
同时,
我们假定从第一行开始考虑, 如果要全部翻转成0, 那么我们当前行的状态将有由下一行同一列的格子翻转来决定.
所以我们不难知道,如果上一行的这个格子是1的话,那么我们当前格子就需要翻转一下. 一直到最后一行翻转完毕,我们最后再判断一下最后一行是否全都是0,就可以确定答案是否存在.
但是,我们这样并不能保证答案最优.. 我们不难发现这种做法依赖于第一行的初始状态. 因为最多只有十列,所以我们不妨把第一行的所有状态都枚举一下,然后都进行答案的查找.
(ps,枚举状态可以用dfs或者二进制. 而我用的dfs搜索过去.)
#include <cstdio>
#include <cstring> using namespace std; int _m[][];
int _ct[][];
int _ans[][];
int tmp[][];
int n, m; bool ishave;
int qstep;
int qsz = ; inline int fff(int val, int mack) {
return val ^ (<<mack);
} void dfs(int now, int step) {
int i, j;
if (now > m) { // 注意,这里需要对矩阵进行操作,但是操作完成后,我们需要把还原原先的矩阵.
// 所以我用了一个临时矩阵来保存.
memcpy(_ct, _m, sizeof(_ct));
for (i=; i<=n; ++i) {
for (j=; j<=m; ++j) {
if (_m[i-][j]) {
_m[i][j] = !_m[i][j];
_m[i-][j] = !_m[i-][j];
_m[i+][j] = !_m[i+][j];
_m[i][j-] = !_m[i][j-];
_m[i][j+] = !_m[i][j+];
tmp[i][j] = ;
step++;
} else tmp[i][j] = ;
}
} for (i=; i<=m; ++i) if (_m[n][i]) { // 当前状态不能全部翻转为0
memcpy(_m, _ct, sizeof(_m));
return ;
}
if (step > qstep) { // 步数判断
memcpy(_m, _ct, sizeof(_m));
return ;
}
qstep = step;
for (i=; i<=n; ++i) { // 字典序判断, 注意,这个题的字典序是从右到左的.
for (j=m; j>=; --j) {
if (tmp[i][j] != _ans[i][j]) goto A;
}
}
A:
if (i<=n && tmp[i][j] < _ans[i][j]) {
ishave = true;
for (i=; i<=n; ++i) {
for (j=; j<=m; ++j)
_ans[i][j] = tmp[i][j];
}
}
memcpy(_m, _ct, sizeof(_m));
return ;
}
// 翻转第一行, 记得翻转的同时,周围的格子也会改变.
dfs(now+, step);
tmp[][now] = ;
_m[][now] = !_m[][now];
_m[][now+] = !_m[][now+];
_m[][now-] = !_m[][now-];
_m[][now] = !_m[][now];
dfs(now+, step+);
tmp[][now] = ;
_m[][now] = !_m[][now];
_m[][now+] = !_m[][now+];
_m[][now-] = !_m[][now-];
_m[][now] = !_m[][now];
}
/*
4 4
1 0 0 1
0 1 1 0
0 0 0 0
0 0 0 0
*/
int main()
{
int i, j;
while (~scanf("%d%d", &n, &m)) {
memset(_ans, 0x3f, sizeof(_ans));
memset(tmp, , sizeof(tmp));
int tmp = ;
int data;
for (i=; i<=n; ++i)
for (j=; j<=m; ++j)
scanf("%d", &_m[i][j]);
ishave = false;
qstep = 0x3f3f3f3f;
dfs(, );
if (ishave) {
for (i=; i<=n; ++i) {
printf("%d", _ans[i][]);
for (j=; j<=m; ++j)
printf(" %d", _ans[i][j]);
printf("\n");
}
} else printf("IMPOSSIBLE\n");
} return ;
}
Find The Multiple POJ - 1426
给你一个数字,要你求出他的倍数,这个倍数由0和1组成.
这个题利用了求模的一个性质 a%mod <==> (b*10+c)%mod 其中 a = b * 10 + c
所以,我们直接暴力搜过去就OK
#include <cstdio> using namespace std; char ans[]; bool isover;
bool dfs(int val, int n, int deep) {
if (!val) { ans[deep] = '\0'; return isover = true; }
if (isover) return true;
if (deep==) { return false; }
ans[deep] = '';
if (dfs(val*%n, n, deep+)) return true;
ans[deep] = '';
if (dfs((val*+)%n, n, deep+)) return true;
return false;
} int main()
{
int n;
while (scanf("%d", &n) && n) {
isover = false;
ans[] = '';
dfs(%n, n, );
printf("%s\n", ans);
}
return ;
}
Oil Deposits HDU - 1241
简单的求连通块的个数. 八个方向的连通块. 直接dfs
#include <cstdio>
#include <cstring> using namespace std; int n, m; char _m[][];
bool vis[][]; bool dfs(int x, int y) {
if (x< || y< || x==n || y==m || vis[x][y] || _m[x][y]=='*') return false;
vis[x][y] = true;
dfs(x-, y); dfs(x+, y); dfs(x, y-); dfs(x, y+);
dfs(x-, y-); dfs(x-, y+); dfs(x+, y-); dfs(x+, y+);
return true;
} int main()
{
int i, j, res;
while (scanf("%d%d", &n, &m) && (n || m)) {
memset(vis, , sizeof(vis));
for (i=; i<n; ++i) scanf("%s", _m[i]);
res = ;
for (i=; i<n; ++i)
for (j=; j<m; ++j)
res += dfs(i, j);
printf("%d\n", res);
} return ;
}
Beautiful Now HDU - 6351
给你两个数字n和k, 问你数字n的数位经过至多k次交换后的最大值和最小值.
因为可以任意次数的交换,所以我们最多交换k次或者交换n的长度次即交换min(len(n), k). 所以可以直接暴力.
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; char s1[];
char s2[];
char ans[];
int len; void dfs1(int now, int k) {
int i;
if (k== || now==len) {
// if (s1[0] == '0') return ;
if (strcmp(ans, s1) > )
strcpy(ans, s1);
return ;
}
if (now == ) {
for (i=now+; i<len; ++i) {
if (s1[i] < s1[now] && s1[i]!='') {
swap(s1[now], s1[i]);
dfs1(now + , k-);
swap(s1[now], s1[i]);
}
}
} else {
for (i=now+; i<len; ++i) {
if (s1[i] < s1[now]) {
swap(s1[now], s1[i]);
dfs1(now + , k-);
swap(s1[now], s1[i]);
}
}
}
dfs1(now+, k);
} void dfs2(int now, int k) {
int i;
if (k== || now==len) {
// if (s2[0] == '0') return ;
if (strcmp(ans, s2) < )
strcpy(ans, s2);
return ;
}
for (i=now+; i<len; ++i) {
if (s2[i] > s2[now]) {
swap(s2[now], s2[i]);
dfs2(now + , k-);
swap(s2[now], s2[i]);
}
}
dfs2(now+, k);
} int main()
{
int t, k;
scanf("%d", &t);
while (t--) { scanf("%s%d", s1, &k);
len = strlen(s1);
strcpy(s2, s1); strcpy(ans, s1);
dfs1(, min(k, len));
printf("%s ", ans); strcpy(ans, s2);
dfs2(, min(k, len));
printf("%s\n", ans);
}
return ;
}
和为K的组合 51Nod - 1268
给你n和数字 和一个k,问你从n个数字中选若干个数字,这些数字的和是否为k
因为n最多只有20个.所以直接爆搜.
#include <cstdio>
#include <algorithm> using namespace std; int n, k;
int arr[]; bool cmp(const int &a, const int &b) {
return a > b;
} bool flag = false; bool dfs(int deep, int val)
{
if (flag) return true;
if (val < ) return false;
if (val == ) return flag=true;
if (deep==n-) {
if (val == arr[deep]) return true;
else return false;
}
return dfs(deep+, val-arr[deep]) || dfs(deep+, val);
} int main()
{
int sum;
while (~scanf("%d%d", &n, &k)) {
sum = k;
int i;
for (i=; i<n; ++i) {
scanf("%d", &arr[i]);
sum -= arr[i];
}
sort(arr, arr+n, cmp);
flag = false;
if (sum> || !dfs(, k)) printf("No\n");
else printf("Yes\n");
} return ;
}
BFS大杂烩
Dungeon Master POJ - 2251
给一个起点,一个终点,多个层.问最短路. 直接bfs.
#include <stdio.h>
#include <string.h>
#include <queue> using namespace std; int l,n,m; char map[][][];
bool vis[][][];
int dir[] = {,,-,,};
int updw[] = {-,}; typedef struct nobe{
int x;
int y;
int l;
int step;
}nobe; int bfs(nobe s)
{
int i;
nobe bb,cc;
queue<nobe> q; q.push(s);
memset(vis,,sizeof(vis));
while(!q.empty()){
bb = q.front();
q.pop(); if(bb.x< || bb.y< || bb.l< || bb.x>=n || bb.y>=m || bb.l>=l) continue;
if('#' == map[bb.l][bb.x][bb.y]) continue;
if('E' == map[bb.l][bb.x][bb.y]) return bb.step;
if(vis[bb.l][bb.x][bb.y]) continue;
vis[bb.l][bb.x][bb.y] = ; for(i=; i<; ++i){
cc.step = bb.step+;
cc.l = bb.l;
cc.x = bb.x+dir[i];
cc.y = bb.y+dir[i+];
q.push(cc);
}
for(i=; i<; ++i){
cc.step = bb.step+;
cc.l = bb.l + updw[i];
cc.x = bb.x;
cc.y = bb.y;
q.push(cc);
}
}
return -;
} int main()
{
int i,j,z,ans;
char str[];
nobe s;
while(scanf("%d%d%d",&l,&n,&m) && (l!= || n!= || m!=)){
for(z=; z<l; ++z){
for(i=; i<n; ++i){
scanf("%s",str);
for(j=; j<m; ++j){
map[z][i][j] = str[j];
if('S'==str[j]){
s.l = z;
s.x = i;
s.y = j;
s.step = ;
}
}
}
}
ans = bfs(s);
if(- == ans){
printf("Trapped!\n");
}else{
printf("Escaped in %d minute(s).\n",ans);
}
} return ;
}
Catch That Cow POJ - 3278
给两个数st, ed. 问你st经过至少多少次变换后可以到达ed. st有以下变化: st+1, st-1, st*2
还是很裸的bfs.
但是有个坑我很久的地方是: G++会wa,C++可以A...原因我也不清楚.
#include <cstdio>
#include <cstring>
#include <queue> using namespace std; struct nobe {
int x;
int step;
nobe () {}
nobe (int xx, int tt) : x(xx), step(tt) {}
}; bool vis[]; int bfs(int n, int k)
{
memset(vis, , sizeof(vis));
nobe now(n, );
queue<nobe> q;
q.push(now);
while (!q.empty()) {
now = q.front(); q.pop();
if (now.x == k) return now.step;
if (vis[now.x]) continue;
vis[now.x] = true;
if (now.x->= && !vis[now.x-]) q.push(nobe(now.x-, now.step+));
if (now.x+<&& !vis[now.x+]) q.push(nobe(now.x+, now.step+));
if (now.x*<&& !vis[now.x*]) q.push(nobe(now.x*, now.step+));
}
} int main()
{
int n, k;
while (~scanf("%d%d", &n, &k)) {
if (n>=k) printf("%d\n", n-k);
else printf("%d\n", bfs(n, k));
} return ;
}
不过也有一种bfs不会wa的写法...然而原因我也还是不清楚....
#include <cstdio>
#include <cstring>
#include <queue> using namespace std; struct nobe {
int x;
int step;
nobe () {}
nobe (int xx, int tt) : x(xx), step(tt) {}
}; int vis[]; int bfs(int n, int k)
{
memset(vis, 0x3f, sizeof(vis));
nobe now(n, );
queue<nobe> q;
q.push(now);
while (!q.empty()) {
now = q.front(); q.pop();
if (now.x == k) return now.step;
if (vis[now.x] < now.step) continue;
vis[now.x] = now.step;
if (now.x->=) q.push(nobe(now.x-, now.step+));
if (now.x+<) q.push(nobe(now.x+, now.step+));
if (now.x*<) q.push(nobe(now.x*, now.step+));
}
return -;
} int main()
{
int n, k;
while (~scanf("%d%d", &n, &k)) {
printf("%d\n", bfs(n, k));
} return ;
}
然后这道题也可以dp做 ---> 因为st-1可能会影响到要更新的dp答案..所以可以暴力点....多做几次dp..多做几十次dp..最后答案就趋近于正确答案了...
当然, 也有别的优秀dp. 但是我不会.
Prime Path POJ - 3126
题目我忘记了. 代码也是copy的以前的. 所以直接粘上来.
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <cstring> using namespace std; bool isprime[]; void getprime()
{
int i, j;
isprime[] = isprime[] = false;
for (i=; i<; ++i) isprime[i] = true;
for (i=; i<; ++i) if (isprime[i])
for (j=*i; j<; j+=i) isprime[j] = false;
} bool vis[]; struct nobe {
int num;
int step;
}; void bfs(int st, int ed)
{
nobe now, tmp;
queue<nobe> q; now.num = st;
now.step = ;
q.push(now); memset(vis, , sizeof(vis));
vis[st] = true;
while (!q.empty()) {
now = q.front(); q.pop(); if (now.num == ed) {
cout << now.step << endl;
return ;
} tmp.step = now.step + ;
int t, pos;
for (int i=; i<; ++i) { t = now.num / ;
pos = now.num + *i - t*;
if (!vis[pos] && isprime[pos] && pos>) {
vis[pos] = true;
tmp.num = pos;
q.push(tmp);
} t = now.num / % ;
pos = now.num + *i - t*;
if (!vis[pos] && isprime[pos]) {
vis[pos] = true;
tmp.num = pos;
q.push(tmp);
} t = now.num/%;
pos = now.num+ *i - t*;
if (!vis[pos] && isprime[pos]) {
vis[pos] = true;
tmp.num = pos;
q.push(tmp);
} t = now.num%;
pos = now.num+i-t;
if (!vis[pos] && isprime[pos]) {
vis[pos] = true;
tmp.num = pos;
q.push(tmp);
}
}
}
cout << "Impossible" << endl;
return ;
} int main()
{
// freopen("E:\\input.txt", "r", stdin);
int t;
int i, j, k;
getprime();
// for (i=1; i<100; ++i) if(isprime[i]) printf("%d ", i);
cin >> t;
int a, b;
while (t--) {
cin >> a >> b;
bfs(a, b);
} return ;
}
Pots POJ - 3414
给你容量为A和B的两个水杯,有三种操作
- FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap; 把水杯水倒掉
- DROP(i) empty the pot i to the drain; 把水倒完
- POUR(i,j) pour from pot i to pot j; after this operation either the pot jis full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j). 把i杯中的水倒到j杯中.
求出是否可以恰好让一杯水中的水为C.
如果可以 输出最小路径, 如果不可以输出impossible
很明显,这个一个bfs+路径记录的题. 我们定义一个nobe fa[A][B][OP]来存路径, A B 表示A杯和B杯中的容量, OP是操作的类型.nobe是bfs的节点.
然后在推进一个新节点之前,把fa也更新一下.最后找到最小路径则根据当前节点的fa进行回溯就OK.
(注意,倒水,填水要注意杯中水的多少. 可以剪掉一些枝.)
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; #define fillb 0
#define filla 1
#define atob 2
#define btoa 3
#define dropa 4
#define dropb 5 struct nobe {
int A;
int B;
int step;
int dir;
nobe () { }
nobe (int aa, int bb, int cc, int type) : A(aa), B(bb), step(cc), dir(type) { }
}; bool vis[][];
nobe fa[][][]; bool bfs(int A, int B, int C) {
memset(vis, , sizeof(vis));
memset(fa, , sizeof(fa));
queue<nobe> q;
int a, b, step, dir;
nobe now(, , , );
q.push(now);
stack<int> st;
while (!q.empty()) {
now = q.front(); q.pop();
a = now.A; b = now.B; step = now.step;
if (vis[a][b]) continue;
vis[a][b] = true;
if (a==C || b== C) {
while (now.A || now.B) {
st.push(now.dir);
now = fa[now.A][now.B][now.dir];
}
// st.push(now.dir);
printf("%d\n", step);
while (!st.empty()) {
dir = st.top(); st.pop();
switch(dir) {
case filla: printf("FILL(1)\n"); break;
case fillb: printf("FILL(2)\n"); break;
case atob: printf("POUR(1,2)\n"); break;
case btoa: printf("POUR(2,1)\n"); break;
case dropa: printf("DROP(1)\n"); break;
case dropb: printf("DROP(2)\n"); break;
}
}
return false;
} if (a && !vis[][b]) {
q.push(nobe(, b, step+, dropa));
fa[][b][dropa] = now;
} if (b && !vis[a][]) {
q.push(nobe(a, , step+, dropb));
fa[a][][dropb] = now;
} if (a!=A) {
if (b) {
if ((A-a) >= b) {
if (!vis[a+b][]) {
q.push(nobe(a+b, , step+, btoa));
fa[a+b][][btoa] = now;
}
} else {
if (!vis[A][b-(A-a)]) {
q.push(nobe(A, b-(A-a), step+, btoa));
fa[A][b-(A-a)][btoa] = now;
}
}
} if (!vis[A][b]) {
q.push(nobe(A, b, step+, filla));
fa[A][b][filla] = now;
}
} if (b!=B) {
if (a) {
if ((B-b) >= a) {
if (!vis[][a+b]) {
q.push(nobe(, a+b, step+, atob));
fa[][a+b][atob] = now;
}
} else {
if (!vis[a-(B-b)][B]) {
q.push(nobe(a-(B-b), B, step+, atob));
fa[a-(B-b)][B][atob] = now;
}
}
} if (!vis[a][B]) {
q.push(nobe(a, B, step+, fillb));
fa[a][B][fillb] = now;
}
}
}
return true;
} int main()
{
int A, B, C;
while (~scanf("%d%d%d", &A, &B, &C)) {
if (bfs(A, B, C)) printf("impossible\n");
}
return ;
}
Fire Game FZU - 2150
给一个一些草地,两个孩子分别从其中一个草地开始放火,问你最后火是否能把草地烧完,如果可以输出时间,如果不可以则输出-1.
注: 火只能在有草地的地方上下左右蔓延.
考虑如果有3个及其以上的分开的草地, 答案肯定是-1.
如果有2个草地,则是两个孩子分别从某点开始放的最小答案.
如果只有一个草地, 答案还是两个孩子分别从某点开始放的最小答案.
如果没有草地,答案就是0.
所以,我们不妨暴力枚举两个草地,从两个草地开始烧火,然后取最小值.如果有答案,那么就是最终答案,如果没有答案,就是没有答案.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> using namespace std; bool vis[][];
char _m[][];
int n, m, qans; struct nobe {
int x;
int y;
int step;
nobe () {}
nobe (int xx, int yy, int sstep) : x(xx), y(yy), step(sstep) {}
}; bool isok() {
int i, j;
for (i=; i<n; ++i)
for (j=; j<m; ++j)
if (_m[i][j]=='#' && !vis[i][j]) return false;
return true;
} int bfs(nobe st1, nobe st2) {
memset(vis, , sizeof(vis));
queue<nobe> q;
nobe now;
q.push(st1);
q.push(st2);
int x, y, step;
while (!q.empty()) {
now = q.front(); q.pop();
x = now.x; y = now.y; step = now.step; if (vis[x][y]) continue;
vis[x][y] = true; if (isok()) return step; if (x->= && _m[x-][y]=='#' && !vis[x-][y]) q.push(nobe(x-, y, step+));
if (x+ <n && _m[x+][y]=='#' && !vis[x+][y]) q.push(nobe(x+, y, step+));
if (y->= && _m[x][y-]=='#' && !vis[x][y-]) q.push(nobe(x, y-, step+));
if (y+ <m && _m[x][y+]=='#' && !vis[x][y+]) q.push(nobe(x, y+, step+));
}
return 0x3f3f3f3f;
} int main()
{
int num;
int t, i, j, x, y;
scanf("%d", &t);
for (int cas=; cas<=t; ++cas) {
scanf("%d%d", &n, &m);
for (i=; i<n; ++i) scanf("%s", _m[i]);
num = ;
memset(vis, , sizeof(vis));
int res = 0x3f3f3f3f;
for (i=; i<n; ++i)
for (j=; j<m; ++j)
for (x=; x<n; ++x)
for (y=; y<m; ++y)
if (_m[i][j]=='#' && _m[x][y]=='#')
res = min(res, bfs(nobe(i, j, ), nobe(x, y, )));
printf("Case %d: %d\n", cas, res==0x3f3f3f3f ? - : res);
} return ;
}
Fire! UVA - 11624
好的,又是火..FFFFFFFFFFFFFFFF
给一个迷宫,火上下左右烧,问人是否可以逃离. (注,有多个起火点!)
我们可以同时bfs. 让火先行,然后处理地图,把下一秒中要烧的地方标识出来, 然后人就自然不能走这些地方了.
如果人可以走出来,那么就输出最小答案.
如果人不能走出来,那么就输出 IMPOSSIBLE
#include <cstdio>
#include <cstring>
#include <queue> using namespace std; int n, m;
char str[][];
bool vis1[][];
bool vis2[][]; struct nobe {
int x;
int y;
int type;
int step;
nobe () { }
nobe (int xx, int yy, int tt, int ss) : x(xx), y(yy), type(tt), step(ss) { }
}; queue<nobe> q; int bfs(nobe st1) {
memset(vis1, , sizeof(vis1));
memset(vis2, , sizeof(vis2));
nobe now; int x, y, type, step;
q.push(st1);
while (!q.empty()) {
now = q.front(); q.pop();
x = now.x; y = now.y; step = now.step; type = now.type; // Fire
if (type && vis2[x][y]) continue;
else if (type) vis2[x][y] = true; if (!type && vis1[x][y]) continue;
else if (!type) vis1[x][y] = true; if (type) {
if (x+<n && (str[x+][y]=='.' || str[x+][y]=='J') && !vis2[x+][y]) {
str[x+][y] = 'F';
q.push(nobe(x+, y, type, step+));
}
if (x->= && (str[x-][y]=='.'|| str[x-][y]=='J') && !vis2[x-][y]) {
str[x-][y] = 'F';
q.push(nobe(x-, y, type, step+));
}
if (y+<m && (str[x][y+]=='.'|| str[x][y+]=='J') && !vis2[x][y+]) {
str[x][y+] = 'F';
q.push(nobe(x, y+, type, step+));
}
if (y->= && (str[x][y-]=='.'|| str[x][y-]=='J') && !vis2[x][y-]) {
str[x][y-] = 'F';
q.push(nobe(x, y-, type, step+));
}
} else {
if (x+==n) return step;
if (x-==-) return step;
if (y+==m) return step;
if (y-==-) return step; if (str[x+][y]=='.' && !vis1[x+][y])
q.push(nobe(x+, y, type, step+));
if (str[x-][y]=='.' && !vis1[x-][y])
q.push(nobe(x-, y, type, step+));
if (str[x][y+]=='.' && !vis1[x][y+])
q.push(nobe(x, y+, type, step+));
if (str[x][y-]=='.' && !vis1[x][y-])
q.push(nobe(x, y-, type, step+));
}
} return ;
} int main()
{
int t, i, j;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
while (!q.empty()) q.pop();
nobe t1, t2;
for (i=; i<n; ++i) {
scanf("%s", str[i]);
for (j=; j<m; ++j) {
if (str[i][j] == 'J') {
t1.x = i; t1.y = j; t1.step = ; t1.type = ;
}
else if (str[i][j] == 'F') {
t2.x = i; t2.y = j; t2.step = ; t2.type = ;
q.push(t2);
}
}
}
int res = bfs(t1);
if (res) printf("%d\n", res);
else printf("IMPOSSIBLE\n");
} return ;
}
迷宫问题 POJ - 3984
bfs简单的记录路径..这道题数据贼秀.. 直接输出样例答案就可以A.....
#include<cstdio>
main(){puts("(0, 0)\n(1, 0)\n(2, 0)\n(2, 1)\n(2, 2)\n(2, 3)\n(2, 4)\n(3, 4)\n(4, 4)");}
非常可乐 HDU - 1495
题目基本忘了. 和刚才水杯的题一样的. 粘以前的代码.
#include <stdio.h>
#include <string.h>
#include <queue> using namespace std; typedef struct nobe{
int s;
int n;
int m;
int step;
}nobe; int vis[][][]; int bfs(nobe start)
{
int S,M,N;
nobe b,c;
queue<nobe> Q; S = start.s;
M = start.m;
N = start.n; start.m = start.n = ;
start.step = ;
Q.push(start);
memset(vis,,sizeof(vis));
while(!Q.empty()){
b = Q.front();
Q.pop(); if((b.m==b.n && ==b.s) || (b.n==b.s && ==b.m) || (b.m==b.s && ==b.n) ){
return b.step;
} if(vis[b.s][b.n][b.m]) continue;
vis[b.s][b.n][b.m] = ; b.step++; c = b;
//1 to 2
if(c.s!=){
if(c.n!=N){
int t = N-c.n;
if(t>=c.s){
c.n += c.s;
c.s = ;
}else{
c.n = N;
c.s -= t;
}
Q.push(c);
}
} c = b;
//1 to 3
if(c.s!=){
if(c.m!=M){
int t = M-c.m;
if(t>=c.s){
c.m += c.s;
c.s = ;
}else{
c.m = M;
c.s -= t;
}
Q.push(c);
} } c = b;
//2 to 3
if(c.n!=){
if(c.m!=M){
int t = M-c.m;
if(t>=c.n){
c.m +=c.n;
c.n = ;
}else{
c.m = M;
c.n-=t;
}
Q.push(c);
} } c = b;
//2 to 1
if(c.n!=){
if(c.s!=S){
int t = S-c.s;
if(t>=c.n){
c.s +=c.n;
c.n = ;
}else{
c.s = S;
c.n-=t;
}
Q.push(c);
}
} c = b;
//3 to 1
if(c.m!=){
if(c.s!=S){
int t = S-c.s;
if(t>=c.m){
c.s +=c.m;
c.m = ;
}else{
c.s = S;
c.m -= t;
}
Q.push(c);
}
} c = b;
//3 to 2
if(c.m!=){
if(c.n!=N){
int t = N-c.n;
if(t>=c.m){
c.n +=c.m;
c.m = ;
}else{
c.n = N;
c.m -= t;
}
Q.push(c);
}
}
}
return -;
} int main()
{
int ans;
nobe start;
while (scanf("%d%d%d",&start.s,&start.n,&start.m) && (start.m!= || start.s!= || start.n!=) ){
start.step = ;
if (start.s&){
ans = -;
}else{
ans = bfs(start);
}
if (-==ans){
printf("NO\n");
}else{
printf("%d\n",ans);
}
} return ;
}
Find a way HDU - 2612
两个人, 多个终点,问到达某个终点的路径之和最小. 坑点就是,两个人的起点不能走!! 不能走!!!
我的做法是bfs2次, 把答案记录在一个二维数组中. 最后取出最小值就是答案.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set> using namespace std; char _m[][]; struct Point {
int x;
int y;
Point () {}
Point (int xx, int yy) : x(xx), y(yy) {}
bool operator < (const Point &a) const {
if (x != a.x) return x < a.x;
return y < a.y;
}
bool operator == (const Point &a) const {
return x==a.x && y==a.y;
}
}ted[]; bool vis[][];
int ans[][];
int times[][]; struct nobe {
Point pt;
int step;
nobe () {}
nobe (Point ppt, int sstep) : pt(ppt), step(sstep) {}
}; int bfs(nobe st, int n, int m) {
memset(vis, , sizeof(vis)); nobe now = st;
queue<nobe> q;
q.push(now);
int x, y;
while (!q.empty()) {
now = q.front(); q.pop();
x = now.pt.x; y = now.pt.y; if (vis[x][y]) continue;
vis[x][y] = true;
if (_m[x][y] == '@') {
ans[x][y] += now.step;
times[x][y]++;
}
if (x->= && (_m[x-][y]=='.' || _m[x-][y]=='@') && !vis[x-][y]) q.push(nobe(Point(x-, y), now.step+));
if (x+< n && (_m[x+][y]=='.' || _m[x+][y]=='@') && !vis[x+][y]) q.push(nobe(Point(x+, y), now.step+));
if (y->= && (_m[x][y-]=='.' || _m[x][y-]=='@') && !vis[x][y-]) q.push(nobe(Point(x, y-), now.step+));
if (y+< m && (_m[x][y+]=='.' || _m[x][y+]=='@') && !vis[x][y+]) q.push(nobe(Point(x, y+), now.step+));
}
return 0x3f3f3f3f;
} int main()
{
// freopen("E:\\input.txt", "r", stdin); int n, m;
int i, j, sz;
while (~scanf("%d%d", &n, &m)) {
// memset(ans, 0, sizeof(ans)); nobe pt1, pt2;
sz = ;
for(i=; i<n; ++i) {
scanf("%s", _m[i]);
for (j=; j<m; ++j) {
if (_m[i][j] == 'Y') {
pt1.pt.x = i; pt1.pt.y = j;
pt1.step = ;
} else if (_m[i][j] == 'M') {
pt2.pt.x = i; pt2.pt.y = j;
pt2.step = ;
} else if (_m[i][j] == '@') {
ted[sz].x = i; ted[sz].y = j;
sz++;
}
}
}
int res = 0x3f3f3f3f;
bfs(pt1, n, m);
bfs(pt2, n, m);
for (i=; i<sz; ++i) {
if (times[ted[i].x][ted[i].y] == )
res = min(ans[ted[i].x][ted[i].y] , res);
times[ted[i].x][ted[i].y] = ;
ans[ted[i].x][ted[i].y] = ;
} printf("%d\n",res);
} return ;
}