题集转自以下链接：
https://blog.csdn.net/shahdza/article/details/7986044
胜利大逃亡(续) HDU - 1429
题意：就是二维地图，有障碍；重点有门，和钥匙（用于开门）。
理解：因为找钥匙，这个解答路径可能会走回头路。
思路：第一遍，因为有时间限制，并且20*20；所以简单bfs，然后MLimit了。感觉就是重复存储点在队列。
那么难点就在于判重了。因为走回头路，简单二维判重肯定不行。
回想和之前炮台那题，因为子弹的原因也是走回头路，所以判重数组多加了一个时间维度。
这题关键因素是钥匙，所以加一个钥匙拥有状态的判重，就ac了。（用2进制状态压缩，这里因为a-j，所以数组开个1024就够了。）
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int n,m,t; char ditu[21][21]; bool vis[1025][21][21]; int Sx,Sy,Fx,Fy; int xx[] = {0,0,1,-1}; int yy[] = {1,-1,0,0}; struct node{ int x,y,step,k=0; node(int a,int b,int c,int d):x(a),y(b),step(c),k(d) {}; }; bool bfs(){ memset(vis,false,sizeof vis); queue<node> q;q.push(node(Sx,Sy,0,0));vis[0][Sx][Sy] = true; while(!q.empty()){ node p = q.front();q.pop(); for(int i=0;i<4;i++){ int x = p.x+xx[i],y = p.y+yy[i]; if(x<0||x>=n||y<0||y>=m||ditu[x][y]=='*'||p.step+1>=t) continue; int step = p.step + 1,k = p.k; if(ditu[x][y]>='A'&&ditu[x][y]<='Z'&&!(p.k&(1<<ditu[x][y]-'A'))) continue; if(ditu[x][y] == '^') {cout<<step<<endl;return true;} if(ditu[x][y]>='a'&&ditu[x][y]<='z') k |= 1<<(ditu[x][y]-'a'); if(vis[k][x][y]) continue; q.push(node(x,y,step,k));vis[k][x][y] = true; } } return false; } int main() { while(cin>>n>>m>>t){ for(int i=0;i<n;i++)for(int j=0;j<m;j++){ char ch = getchar();while(ch==' '||ch==' ') ch = getchar(); ditu[i][j] = ch; if(ch=='^') Fx = i,Fy = j; else if(ch=='@') Sx = i,Sy = j; } if(!bfs()) puts("-1"); } return 0; }
这题给我启发就是，判重作用在于剪枝，避免重复的入队操作。那么关键在于什么？关键在于点状态更新，并且取决于什么要素关键，炮台那题，因为子弹原因，时间是关键。这题因为门的原因，钥匙是关键。所以添加关键要素的判重数组是解题关键。
Key Task HDU - 1885
题意与上题一样。但是地图大小和钥匙，门出口数量不同。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <map> using namespace std; int n,m; char ditu[101][101]; bool vis[17][101][101]; int Sx,Sy,Fx,Fy; int xx[] = {0,0,1,-1}; int yy[] = {1,-1,0,0}; struct node{ int x,y,step,k=0; node(int a,int b,int c,int d):x(a),y(b),step(c),k(d) {}; }; int mp[5]; bool bfs(){ memset(vis,false,sizeof vis); queue<node> q;q.push(node(Sx,Sy,0,0));vis[0][Sx][Sy] = true; while(!q.empty()){ node p = q.front();q.pop(); for(int i=0;i<4;i++){ int x = p.x+xx[i],y = p.y+yy[i]; if(x<0||x>=n||y<0||y>=m||ditu[x][y]=='#') continue; int step = p.step + 1,k = p.k; if(ditu[x][y] == 'X') {cout<<"Escape possible in "<<step<<" steps."<<endl;return true;} if(ditu[x][y]>='A'&&ditu[x][y]<='Z'&&!(p.k&(1<<mp[ditu[x][y]-'A']))) continue; if(ditu[x][y]>='a'&&ditu[x][y]<='z') k |= 1<<mp[ditu[x][y]-'a']; if(vis[k][x][y]) continue; q.push(node(x,y,step,k));vis[k][x][y] = true; } } return false; } int main() { mp['B'-'A'] = 0,mp['Y'-'A'] = 1,mp['R'-'A'] = 2,mp['G'-'A'] = 3; while(cin>>n>>m&&n&&m){ for(int i=0;i<n;i++)for(int j=0;j<m;j++){ char ch = getchar();while(ch==' '||ch==' ') ch = getchar(); ditu[i][j] = ch; if(ch=='X') Fx = i,Fy = j; else if(ch=='*') Sx = i,Sy = j; } if(!bfs()) puts("The poor student is trapped!"); } return 0; }
扩展思考：我这里想到如果钥匙并非永久产品而是一次性，那该怎么办？
我感觉难点可能在于不止走一次回头路。
我一开始能想到就是：像多重背包操作一样，将问题转化为0-1，多个相同门和钥匙，对应将他们分类成不同颜色。额，好像不行，因为你不清楚那个钥匙对应哪个门即为最优。。。。
那判重函数多加一维度，有什么颜色钥匙，并且多一个钥匙数量的维度。
超级密码HDU - 1226
算法：BFS
思路：BFS向下操作，*进制数+构成数 然后 对N求余 得到 的余数，因为是要正整数倍，所以当余数为0则为答案。
K1%N = K2%N；（K1*C+M）%N = （K2*C+M）%N ；所以余数可以作为判重点。相同余数不需要重复入队。
用数组记录答案长度，因为BFS是有层次性，所以超过500就可以判负了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> using namespace std; int N,C,M; int yS[17],ySlen; int vis[5005],pre[5005],ans[5005],cnt[5005]; void init(){ memset(vis,0,sizeof vis); memset(cnt,0,sizeof cnt); memset(pre,-1,sizeof pre); scanf("%d%d%d",&N,&C,&M); for(int i=0;i<M;i++){ char ch = getchar();while(ch == ' '|| ch == ' ') ch = getchar(); if(ch>='0'&&ch<='9') yS[i] = ch - '0'; else yS[i] = ch - 'A' + 10; } sort(yS,yS+M); ySlen = unique(yS,yS+M) - yS; } void showAns(int num){ if(num == -1) return ; showAns(pre[num]); if(ans[num]<10) printf("%d",ans[num]); else printf("%c",ans[num] - 10 + 'A'); } bool solve(){ queue<int> q; for(int i=0;i<ySlen;i++){ if(!yS[i]) continue; int tnt = yS[i] % N; if(vis[tnt]) continue; vis[tnt] = 1;cnt[tnt] = 1; ans[tnt] = yS[i]; if(!tnt) return true; q.push(tnt); } while(!q.empty()){ int now = q.front();q.pop(); if(cnt[now]>500) return false; for(int i=0;i<ySlen;i++){ int tnt = (now*C + yS[i]) % N; if(vis[tnt]) continue; vis[tnt] = 1;cnt[tnt] = cnt[now] + 1; ans[tnt] = yS[i];pre[tnt] = now; if(!tnt) return true; q.push(tnt); } } return false; } int main() { int _;scanf("%d",&_); while(_--){ init(); if(!N) {if(!yS[0]) puts("0");else puts("give me the bomb please");} else{ if(!solve()) puts("give me the bomb please"); else showAns(0),puts(""); } } return 0; }
Different DigitsHDU - 1664
算法：数论+BFS
思路：感觉这题集出得挺不错，每道题总与上一道题有关联。这一题和上一题一样，也是求N的正整数倍。所以也是余数下手。
但是这题巧妙在于，最优解是，答案需尽量少不同数字构成且最小。
这里牵扯的数论就是：
很好理解：求10进制的余数，（*10+1）MOD，因为只加一个数字的求余存在一个循环，存在0则为答案。余数相同，就互减得到答案，互减将余数减掉就是N的整数倍了。
所以一个整数一定存在一个正整数倍的数，且由0和1的数构成。
所以，两不同数字就构成本题答案；
那么这题剩下就是求一个最优最小解，即不同数字的数量相同求最小。
分两层，第一层只用一个数叠加求，得到答案就是最优。得不到去第二层，循环从不同两个数字组合求出答案。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> using namespace std; const int inf = 2e9; int N,ansLen; bool vis[65536]; string ans,res; bool gO(int x){ memset(vis,false,sizeof vis); int tmp = 0;res = ""; while(1){ tmp = (tmp*10+x) % N; if(vis[tmp]) return false; vis[tmp] = true; res += '0' + x; if(!tmp){ if(ansLen == inf||ans.length()>res.length()){ ans = res;ansLen = res.length();return true; } return false; } } } int val[65536],pre[65536],cnt[65536]; void getAns(int x){ if(x==-1) return ; getAns(pre[x]); res += '0' + val[x]; } bool gT(int x,int y){ memset(vis,false,sizeof vis); memset(pre,-1,sizeof pre); memset(cnt,0,sizeof cnt); queue<int> q; int fk,num[2]={x,y}; if(x) { fk = x%N;vis[fk] = true,val[fk] = x,cnt[fk] = 1;q.push(fk); } fk = y%N; if(!vis[fk]) {vis[fk] = true,val[fk] = y,cnt[fk] = 1;q.push(fk);} while(!q.empty()){ int now = q.front();q.pop(); if(cnt[now]>ansLen) return false; for(int i=0;i<2;i++){ fk = (now*10 + num[i]) % N; if(vis[fk]) continue; vis[fk] = true,val[fk] = num[i],cnt[fk] = cnt[now] + 1,pre[fk] = now; if(!fk){ res = "";getAns(0); if(ansLen==inf||ans.length()>res.length()||(ans.length()==res.length()&&res<ans)){ ans = res;ansLen = res.length(); return true; } return false; } q.push(fk); } } return false; } int main() { while(cin>>N&&N){ int flag = 0; ansLen = inf;ans = ""; for(int i=1;i<10;i++) if(gO(i)) flag = 1; if(flag) {cout<<ans<<endl;continue;} for(int i=0;i<10;i++) for(int j=i+1;j<10;j++) gT(i,j); cout<<ans<<endl; } return 0; }
Pusher HDU - 2821
算法：枚举+dfs（简单模拟）
题意：类似手机游戏，一副25*25的地图，有多个障碍物，障碍物由字母表示，a为一方块，b为内嵌的2方块，以此类推。
球体，要选取一个地方起步（这里我用全地图枚举），进行弹射必须有一个空格当空隙。
起步后，方向不变，直到撞到方块才停下，且推方块向后一步，方块数减一，剩余方块积累到后一步。后一步如果是地图外，则起步方块消失。
如果球飞出地图，则失败。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> using namespace std; int n,m; int ditu[26][26],sum; int xx[4] = {0,0,1,-1}; int yy[4] = {1,-1,0,0}; char dire[5] = "RLDU"; int len; char ans[2500]; void init(){ sum = 0,len=0; memset(ditu,0,sizeof ditu); for(int i=0;i<n;i++)for(int j=0;j<m;j++){ char ch = getchar(); while(ch==' '||ch==' ') ch = getchar(); if(ch>='a'&&ch<='z') ditu[i][j] += ch - 'a' + 1, sum+= ditu[i][j]; } } bool check(int a,int b,int c){ int x = a + xx[c] , y = b + yy[c]; if(x<0||x>=n||y<0||y>=m||ditu[x][y]!=0) return false; return true; } int check3(int x,int y){ if(x<0||x>=n||y<0||y>=m) return 0; if(ditu[x][y]!=0) return 1; return 2; } bool check2(int &a,int &b,int c){ while(1){ a += xx[c],b += yy[c]; int tnt = check3(a,b); if(tnt==0) return false; if(tnt==1) return true; } } bool dfs(int x,int y,int z){ if(z==0) return true; for(int i=0;i<4;i++){ if(!check(x,y,i)) continue; int a = x,b = y; if(!check2(a,b,i)) continue; //cout<<x<<" "<<y<<" "<<a<<" "<<b<<" "<<z<<endl; bool flag = false; if(check3(a+xx[i],b+yy[i])!=0) flag = true; int fk = ditu[a][b],fkk,c; if(flag){ fkk = ditu[a+xx[i]][b+yy[i]]; ditu[a+xx[i]][b+yy[i]] += fk - 1; c = z - 1; }else c = z - fk; ditu[a][b] = 0; ans[len++] = dire[i]; if(dfs(a,b,c)) return true; len--; ditu[a][b] = fk; if(flag) ditu[a+xx[i]][b+yy[i]] = fkk; } return false; } int main() { while(cin>>m>>n){ init(); //cout<<sum<<endl; //for(int i=0;i<n;i++){for(int j=0;j<m;j++) cout<<ditu[i][j]<<" ";cout<<endl;} int cp = 1; for(int i=0;i<n&&cp;i++)for(int j=0;j<m&&cp;j++) if(ditu[i][j]==0&&dfs(i,j,sum)) { printf("%d %d ",i,j); ans[len] = ' ';cout<<ans<<endl; cp = 0; } } return 0; }
Tempter of the Bone IIHDU - 2128
算法：BFS/DFS
题意：就是给一个有障碍的地图，图上有炸弹推，经过就可以捡上，不过只能捡一次。炸弹可以炸墙，不过算一步。
判重就简单的3维，坐标加炸弹。
BFS
这里我BFS，直接模拟，找到答案直接输出，然后wrong了。
后面看别人代码，得知原因，因为，我直接将炸开炸弹，与进入墙体两步，结合在一层进行模拟；
容易导致BFS跨步错误，就像之前做过的一道题，情侣被鬼追，G - Nightmare Ⅱ HDU - 3085 。这题我在kuangbin题集做了解析。
这里类似2步走，第二步vis标记会导致其他第一步入队而出现答案错误，wrong。
这里我是看别人代码学的操作，将vis移到出队再加，然后答案，通过ans记录，并进行求最短剪枝。这里就相当于将vis标记放到下一层去判断，虽然会增加入队冗余，但是ans优化也减了一部分。
一开始码的时候不知道这样对不对？不管先试了再说。然后就AC了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> using namespace std; const int inf = 2e9; int n,m,ans; int Sx,Sy; char ditu[9][9]; bool vis[9][9][600]; int xx[] = {1,-1,0,0}; int yy[] = {0,0,1,-1}; void init(){ memset(vis,false,sizeof vis); ans = inf; for(int i=0;i<n;i++)for(int j=0;j<m;j++){ char ch = getchar();while(ch==' '||ch==' ') ch = getchar(); ditu[i][j] = ch; if(ch=='S') Sx = i,Sy = j; } } struct node{ int x,y,step,exp; bool state[9][9]; node(int a,int b,int c,int d):x(a),y(b),step(c),exp(d) { memset(state,false,sizeof state); }; }; bool bfs(){ queue<node> q;q.push(node(Sx,Sy,0,0)); while(!q.empty()){ node p = q.front();q.pop(); vis[p.x][p.y][p.exp] = true; if(p.x>=ans) continue; for(int i=0;i<4;i++){ node now = p; now.x = p.x + xx[i] , now.y = p.y + yy[i],now.step++; if(now.x<0||now.x>=n||now.y<0||now.y>=m) continue; if(ditu[now.x][now.y]=='D') {ans = min(ans,now.step);continue;} if(ditu[now.x][now.y]=='X'&&!now.state[now.x][now.y]){ if(now.exp==0) continue; else now.state[now.x][now.y] = true,now.exp--,now.step++; } if(ditu[now.x][now.y]>='0'&&ditu[now.x][now.y]<='9'&&!now.state[now.x][now.y]){ now.state[now.x][now.y] = true; now.exp += ditu[now.x][now.y] - '0'; } if(vis[now.x][now.y][now.exp]) continue; q.push(now); } } if(ans==inf) return false; else {cout<<ans<<endl;return true;} } int main() { while(cin>>n>>m&&n&&m){ init(); if(!bfs()) puts("-1"); } return 0; }
后面想验证一下，到底是不是炸弹并步走，才导致的wrong，我就尝试将炸弹和入墙分为两步，再不同层进行。结果也AC。所以之前wrong就是BFS跨步走问题。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> using namespace std; const int inf = 2e9; int n,m; int Sx,Sy; char ditu[9][9]; bool vis[9][9][600]; int xx[] = {1,-1,0,0}; int yy[] = {0,0,1,-1}; void init(){ memset(vis,false,sizeof vis); for(int i=0;i<n;i++)for(int j=0;j<m;j++){ char ch = getchar();while(ch==' '||ch==' ') ch = getchar(); ditu[i][j] = ch; if(ch=='S') Sx = i,Sy = j; } } struct node{ int x,y,step,exp; int state[9][9]; node(int a,int b,int c,int d):x(a),y(b),step(c),exp(d) { memset(state,0,sizeof state); }; }; bool bfs(){ queue<node> q;q.push(node(Sx,Sy,0,0));vis[Sx][Sy][0] = true; while(!q.empty()){ node p = q.front();q.pop(); if(ditu[p.x][p.y]=='X'&&p.state[p.x][p.y]==2){ p.state[p.x][p.y]=1; p.step++; q.push(p); continue; } for(int i=0;i<4;i++){ node now = p; now.x = p.x + xx[i] , now.y = p.y + yy[i],now.step++; if(now.x<0||now.x>=n||now.y<0||now.y>=m) continue; if(ditu[now.x][now.y]=='D') {cout<<now.step<<endl;return true;} if(ditu[now.x][now.y]=='X'&&now.state[now.x][now.y]==0){ if(now.exp==0) continue; else { now.state[now.x][now.y] = 2,now.exp--; if(vis[now.x][now.y][now.exp]) continue; vis[now.x][now.y][now.exp] = true; q.push(now);continue; } } if(ditu[now.x][now.y]>='0'&&ditu[now.x][now.y]<='9'&&!now.state[now.x][now.y]){ now.state[now.x][now.y] = 1; now.exp += ditu[now.x][now.y] - '0'; } if(vis[now.x][now.y][now.exp]) continue; vis[now.x][now.y][now.exp] = true; q.push(now); } } return false; } int main() { while(cin>>n>>m&&n&&m){ init(); if(!bfs()) puts("-1"); } return 0; }
IDEA*
这里我DFS模拟，我决策函数用哈夫曼函数。然后模拟与上面BFS无疑，重点这里DFS也需要一步步来,因为想求得即最优。
可能存在没有答案，所以limit需要上限，8*8 = 64，64-2 = 62；然后取7个空作9炸弹，剩下55个空都是墙，然而63>55,所以55个墙为最坏情况，63+55 = 108步。上限为108；
（这里最坏情况假设，每次拿最近的炸弹必须用完之前的，每细想其他细节，所以大概就估算）
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> #include <cmath> using namespace std; const int inf = 2e9; int n,m; int Sx,Sy,Fx,Fy; int limit,nextd; char ditu[9][9]; bool vis[9][9][600]; int state[9][9]; int xx[] = {1,-1,0,0}; int yy[] = {0,0,1,-1}; void init(){ memset(vis,false,sizeof vis); memset(state,0,sizeof state); for(int i=0;i<n;i++)for(int j=0;j<m;j++){ char ch = getchar();while(ch==' '||ch==' ') ch = getchar(); ditu[i][j] = ch; if(ch=='S') Sx = i,Sy = j;if(ch=='D') Fx = i,Fy = j; } } int check(int x,int y){ return abs(x-Fx) + abs(y-Fy); } bool dfs(int x,int y,int step,int exp,int limit){ int h = check(x,y); if(h+step>limit){ nextd = min(h+step,nextd); return false; } if(h==0) {cout<<step<<endl;return true;} if(ditu[x][y]=='X'&&state[x][y]==2){ state[x][y] = 1; if(dfs(x,y,step+1,exp,limit)) return true; return false; } for(int i=0;i<4;i++){ int a = x + xx[i],b = y + yy[i],c = step+1,d = exp; if(a<0||a>=n||b<0||b>=m) continue; int flag = 0; if(ditu[a][b]=='X'&&!state[a][b]){ if(d==0) continue; else{ d--,state[a][b] = 2,flag = 1; if(vis[a][b][d]) continue; vis[a][b][d] = true; if(dfs(a,b,c,d,limit)) return true; vis[a][b][d] = false; if(flag) state[a][b] = 0; continue; } } if(ditu[a][b]>='0'&&ditu[a][b]<='9'&&!state[a][b]) state[a][b] = 1,flag = 1,d += ditu[a][b] - '0'; if(vis[a][b][d]) continue; vis[a][b][d] = true; if(dfs(a,b,c,d,limit)) return true; vis[a][b][d] = false; if(flag) state[a][b] = 0; } return false; } int main() { while(cin>>n>>m&&n&&m){ init(); int flag = 0;vis[Sx][Sy][0] = true; for(limit = check(Sx,Sy);limit<=102;){ nextd = inf; if(dfs(Sx,Sy,0,0,limit)) {flag = 1;break;} limit = nextd; }if(flag) continue; puts("-1"); } return 0; }
Ali and BabaHDU - 4101
算法：BFS + 博弈判奇偶
难点：题目在于理解。因为博弈，两人都是以自己最优的思路操作。所以胜负关键点很重要。
胜负关键点在于，谁最后打开宝藏包围圈谁输。
题意：一副地图，只有一个宝藏，然后存在石头推（以数字表示，<100），然后每人每步可以打碎一个石头。然后走路不算操作数。
思路：第一步：先标记从宝藏出发能达到的0点（包括宝藏自身也要标记），因为到达这里就表示已经赢了；这里如果标记点，存在于边界，就表示Ali不用破碎石头就能拿宝藏，所以Ali Win；
第二步：获取走到胜负关键点的总操作数。（胜负关键点就是谁可以走到那些上一步的标记点，因为谁都不想帮别人破最后的石头，所以就会选择破其他无关石头，所以要记录所有外围石头数即总操作数）；这里简单联想一下，就是这一步宝藏外围一定有一个石头包围圈即屏障，谁先打破谁输。
第三步：第二步的重点在于记录石头数量，因为最后屏障是一个石头数量1的包围圈，这个包围圈石头数不用记录；然后所有外围石头数量总和判奇偶，奇数表示Baba要去破壁，所以Ali Win；反之同义。
失误：这里我wrong了；有两点：1）Baba Win 我写成了BaBa Win;2)第二步，我只用了（0，0）入队判断，其实不行，因为包围圈可能已经覆盖到边界了。所以要所有边界点入队判断；
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> #include <cmath> using namespace std; int n,m,Sx,Sy,ans; int ditu[303][303]; bool vis[303][303],vis2[303][303]; int xx[] = {1,-1,0,0}; int yy[] = {0,0,1,-1}; void init(){ memset(vis,false,sizeof vis); memset(vis2,false,sizeof vis2); ans = 0; } struct node{ int x,y; node(int a,int b):x(a),y(b) {}; }; bool bfs(){ queue<node> q; q.push(node(Sx,Sy));vis2[Sx][Sy] = true; while(!q.empty()){ node p = q.front();q.pop(); if(p.x==0||p.x==n-1||p.y==0||p.y==m-1) return true; for(int i=0;i<4;i++){ int x = p.x + xx[i],y = p.y + yy[i]; if(x<0||x>=n||y<0||y>=m||ditu[x][y]!=0||vis2[x][y]) continue; q.push(node(x,y)); vis2[x][y] = true; } } return false; } bool check(int x,int y){ for(int i=0;i<4;i++) if(vis2[x+xx[i]][y+yy[i]]) return true; return false; } void bfs2(){ queue<node> q; for(int j=0;j<m;j++){ if(!vis[0][j]) q.push(node(0,j)),vis[0][j] = true,ans += ditu[0][j]; if(!vis[n-1][j]) q.push(node(n-1,j)),vis[n-1][j] = true,ans += ditu[n-1][j]; } for(int i=0;i<n;i++){ if(!vis[i][0]) q.push(node(i,0)),vis[i][0] = true,ans += ditu[i][0]; if(!vis[i][m-1]) q.push(node(i,m-1)),vis[i][m-1] = true,ans += ditu[i][m-1]; } while(!q.empty()){ node p = q.front();q.pop(); if(check(p.x,p.y)) {ans --;continue;} for(int i=0;i<4;i++){ int x = p.x + xx[i],y = p.y + yy[i]; if(x<0||x>=n||y<0||y>=m||vis[x][y]) continue; q.push(node(x,y)); vis[x][y] = true,ans+=ditu[x][y]; } } //cout<<ans<<endl; if(ans%2) puts("Ali Win"); else puts("Baba Win"); } void show(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cout<<vis2[i][j]<<" ";cout<<endl; } } int main() { while(~scanf("%d%d",&n,&m)){ init(); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ scanf("%d",&ditu[i][j]); if(ditu[i][j]==-1) Sx = i,Sy = j; } if(bfs()){ puts("Ali Win"); }else bfs2(); //show(); } return 0; }
Ancient Messages HDU - 3839
算法：BFS
题意：就是给你一副图，图里面有很多埃及象形字，然后图像由像素0，1构成，1表示颜色黑，0则表示白。
难点：第一点在于怎么巧妙区别埃及象形字？ 每个埃及象形字都是有闭合空间并且数量对于每个埃及象形字不同，所以可以从空白入手。
第二点在于如何区分埃及象形字内的空白与外空白？ 这里题目给出了关键点，就是每两个埃及象形字必不连接且不嵌套。并且黑色部分永远相连不断。
思路：预处理：这里使用十六进制代表二进制像素，所以需要还原。
第一步：从边界开始读空白，进行白色BFS，把所有埃及象形字的外空白标记。
第二步：从上到下从左到右，找埃及象形字，遇到则开始黑色BFS，每遇到白色没标记则开始白色BFS标记；重点记录，遇到几次空白，即这个埃及象形字有多少闭合空白空间。从而区分这个是什么埃及象形字；
第三步：通过BFS得出的埃及象形字数量，然后字典输出即可AC。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <map> #include <cmath> using namespace std; int n,m,ditu[202][202],ans[8],cas=1; int gg[] = {1,5,3,2,4,0}; char gk[] = {'A','D','J','K','S','W'}; int xx[] = {1,-1,0,0}; int yy[] = {0,0,1,-1}; bool vis[202][202]; struct node{ int x,y; node(int a,int b):x(a),y(b) {}; }; void bfs_white(int a,int b){ queue<node> q; q.push(node(a,b)),vis[a][b] = true; while(!q.empty()){ node p = q.front();q.pop(); for(int i=0;i<4;i++){ int x = p.x + xx[i],y = p.y + yy[i]; if(x<0||x>=n||y<0||y>=m||ditu[x][y]||vis[x][y]) continue; q.push(node(x,y)),vis[x][y] = true; } } return ; } void bfs_black(int a,int b){ queue<node> q; int acer = 0; q.push(node(a,b)),vis[a][b] = true; while(!q.empty()){ node p = q.front();q.pop(); for(int i=0;i<4;i++){ int x = p.x + xx[i],y = p.y + yy[i]; if(x<0||x>=n||y<0||y>=m||vis[x][y]) continue; if(ditu[x][y]) q.push(node(x,y)),vis[x][y] = true; else bfs_white(x,y),acer++; } } ans[acer]++; return ; } void show(){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cout<<ditu[i][j]<<" ";cout<<endl; } } int main() { while(~scanf("%d%d",&n,&m)){ if(!n&&!m) break; for(int i=0;i<n;i++) for(int j=0,z=0;j<m;j++){ char ch = getchar(); while(ch==' '||ch==' ') ch = getchar(); int num; if(ch>='a'&&ch<='z') num = ch-'a'+10; else num = ch-'0'; if(num>=8) ditu[i][z++] = 1,num-=8; else ditu[i][z++] = 0; if(num>=4) ditu[i][z++] = 1,num-=4; else ditu[i][z++] = 0; if(num>=2) ditu[i][z++] = 1,num-=2; else ditu[i][z++] = 0; if(num>=1) ditu[i][z++] = 1; else ditu[i][z++] = 0; }m*=4; //show(); memset(ans,0,sizeof ans); memset(vis,false,sizeof vis); //边界找0 for(int j=0;j<m;j++){ if(!vis[0][j]&&ditu[0][j]==0) bfs_white(0,j); if(!vis[n-1][j]&&ditu[n-1][j]==0) bfs_white(n-1,j); } for(int i=0;i<n;i++){ if(!vis[i][0]&&ditu[i][0]==0) bfs_white(i,0); if(!vis[i][m-1]&&ditu[i][m-1]==0) bfs_white(i,m-1); } //找图像 for(int i=0;i<n;i++)for(int j=0;j<m;j++) if(!vis[i][j]&&ditu[i][j]) bfs_black(i,j); printf("Case %d: ",cas++); for(int i=0;i<6;i++) for(int j=0;j<ans[gg[i]];j++) printf("%c",gk[i]); puts(""); } return 0; }