敲了一上午 意外的超內存了一次 ！！！！！開始數組開的太大
題意是給你一個棋盤， 有5種不同的棋子，一個車 一個馬 一個炮（每個只有一個） 走法按正常棋子走法一樣 還有對面一個將 和眾多小兵（將和小兵都是不能動的）
問你最少需要走幾步能殺死將；
思路： 明顯的廣搜題
結構體裡有車馬炮分別的坐標和當前的步數， 按正常的廣搜做； 每次都有三種走法 （車 馬 炮 ） 而對車又有兩種走法 對馬有8種走法 （注意蹩馬的判斷） 對炮友2種走法 注意和車的區別 （車可以都將而炮不能） 然後正常做 判斷能不能殺死將車馬好說 炮就另加判斷 見代碼
#include#include #include #include using namespace std; int mark[11][11][11][11][11][11]; char map[15][15]; int n,m; int dir[8][2]={-2,1, -1,2, 1,2, 2,1, 2,-1, 1,-2, -1,-2, -2,-1}; int dirt[4][2]={0,1,0,-1,1,0,-1,0}; int xx,yy; struct node { int cx,cy; int mx,my; int px,py; int step; }a,b; int min(int x,int y) { return x<y?x:y; } int max(int x,int y) { return x>y?x:y; } int bfs(int ci,int cj,int mi,int mj,int pi,int pj) { int i,j; memset(mark,0,sizeof(mark)); a.cx=ci; a.cy=cj; a.mx=mi; a.my=mj; a.px=pi; a.py=pj; a.step=0; mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]=1; queue<node>q; q.push(a); int flash=0; while(!q.empty()) { b=q.front(); q.pop(); if(map[b.cx][b.cy]=='S'||map[b.mx][b.my]=='S') { flash=1; printf("%d\n",b.step); break; } else if(b.px==xx) { int cont=0; for(i=min(b.py,yy)+1;i<max(b.py,yy);i++) { if(map[b.px][i]=='D') cont++; else if(i==b.cy&&b.px==b.cx) cont++; else if(i==b.my&&b.px==b.mx) cont++; } if(cont==1) { flash=1; printf("%d\n",b.step+1); break; } } else if(b.py==yy) { int cont=0; for(i=min(b.px,xx)+1;i<max(b.px,xx);i++) { if(map[i][b.py]=='D') cont++; else if(i==b.cx&&b.py==b.cy) cont++; else if(i==b.mx&&b.py==b.my) cont++; } if(cont==1) { flash=1; printf("%d\n",b.step+1); break; } } for(i=0;i<8;i++) { a=b; a.step=b.step+1; a.mx=b.mx+dir[i][0]; a.my=b.my+dir[i][1]; if(a.mx<0||a.mx>=n||a.my<0||a.my>=m) continue; if(map[a.mx][a.my]=='D') continue; if(a.mx==a.cx&&a.my==a.cy) continue; if(a.mx==a.px&&a.my==a.py) continue; if(i==0||i==7) { if(map[b.mx-1][b.my]=='D'||map[b.mx-1][b.my]=='S') continue; else if(b.mx-1==b.cx&&b.my==b.cy) continue; else if(b.mx-1==b.px&&b.my==b.py) continue; } else if(i==1||i==2) { if(map[b.mx][b.my+1]=='D'||map[b.mx][b.my+1]=='S') continue; else if(b.mx==b.cx&&b.my+1==b.cy) continue; else if(b.mx==b.px&&b.my+1==b.py) continue; } else if(i==3||i==4) { if(map[b.mx+1][b.my]=='D'||map[b.mx+1][b.my]=='S') continue; else if(b.mx+1==b.cx&&b.my==a.cy) continue; else if(b.mx+1==b.px&&b.my==a.py) continue; } else { if(map[b.mx][b.my-1]=='D'||map[b.mx][b.my-1]=='S') continue; else if(b.mx==b.cx&&b.my-1==b.cy) continue; else if(b.mx==b.px&&b.my-1==b.py) continue; } //printf("%d $$$ %d\n",b.mx,b.my); if(mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]==0) { mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]=1; q.push(a); } } for(i=0;i<4;i++) { for(j=1;j<=10;j++) { a=b; a.step=b.step+1; a.cx=dirt[i][0]*j+b.cx; a.cy=dirt[i][1]*j+b.cy; if(a.cx<0||a.cx>=n||a.cy<0||a.cy>=m) break; if(map[a.cx][a.cy]=='D') break; if(a.cx==a.mx&&a.cy==a.my) break; if(a.cx==a.px&&a.cy==a.py) break; if(mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]==0) { mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]=1; q.push(a); } } } for(i=0;i<4;i++) for(j=1;j<=10;j++) { a=b; a.step=b.step+1; a.px=dirt[i][0]*j+b.px; a.py=dirt[i][1]*j+b.py; if(a.px<0||a.px>=n||a.py<0||a.py>=m) break; if(map[a.px][a.py]=='D') break; if(map[a.px][a.py]=='S') break; if(a.px==a.cx&&a.py==a.cy) break; if(a.px==a.mx&&a.py==a.my) break; if(mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]==0) { mark[a.cx][a.cy][a.mx][a.my][a.px][a.py]=1; q.push(a); } } } if(flash==0) printf("OH!That's impossible!\n"); return 0; } int main() { int i,j; int d=1; while(~scanf("%d%d",&n,&m)) { int ci,cj,mi,mj,pi,pj; for(i=0;i<n;i++) scanf("%s",map[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) { if(map[i][j]=='C') { ci=i; cj=j; } else if(map[i][j]=='M') { mi=i; mj=j; } else if(map[i][j]=='P') { pi=i; pj=j; } else if(map[i][j]=='S') { xx=i; yy=j; } } printf("Scenario #%d\n",d++); bfs(ci,cj,mi,mj,pi,pj); printf("\n"); } return 0; }
