文章目錄
- 題目
- 深搜代碼
- 寬搜代碼
- 深搜數據
- 演示圖
- 總結
題目
1804:小游戲
總時間限制: 1000ms 內存限制: 65536kB
描述
一天早上，你起床的時候想：“我編程序這么牛，為什么不能靠這個賺點小錢呢？”因此你決定編寫一個小游戲。 游戲在一個分割成w * h個正方格子的矩形板上進行。如圖所示，每個正方格子上可以有一張游戲卡片，當然也可以沒有。 當下面的情況滿足時，我們認為兩個游戲卡片之間有一條路徑相連： 路徑只包含水平或者豎直的直線段。路徑不能穿過別的游戲卡片。但是允許路徑臨時的離開矩形板。下面是一個例子：
這里在 (1, 3)和 (4, 4)處的游戲卡片是可以相連的。而在 (2, 3) 和 (3, 4) 處的游戲卡是不相連的，因為連接他們的每條路徑都必須要穿過別的游戲卡片。 你現在要在小游戲里面判斷是否存在一條滿足題意的路徑能連接給定的兩個游戲卡片。
輸入
輸入包括多組數據(不多于10組)。一個矩形板對應一組數據。每組數據包括的第一行包括兩個整數w和h (1 <= w, h <= 75)，分別表示矩形板的寬度和長度。下面的h行，每行包括w個字符，表示矩形板上的游戲卡片分布情況。使用‘X’表示這個地方有一個游戲卡片；使用空格表示這個地方沒有游戲卡片。
之后的若干行上每行上包括4個整數x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h)。給出兩個卡片在矩形板上的位置（注意：矩形板左上角的坐標是(1, 1)）。輸入保證這兩個游戲卡片所處的位置是不相同的。如果一行上有4個0，表示這組測試數據的結束。
如果一行上給出w = h = 0，那么表示所有的輸入結束了。
輸出
對每一個矩形板，輸出一行“Board #n:”，這里n是輸入數據的編號。然后對每一組需要測試的游戲卡片輸出一行。這一行的開頭是“Pair m: ”，這里m是測試卡片的編號（對每個矩形板，編號都從1開始）。接下來，如果可以相連，找到連接這兩個卡片的所有路徑中包括線段數最少的路徑，輸出“k segments.”，這里k是找到的最優路徑中包括的線段的數目；如果不能相連，輸出“impossible.”。
每組數據之后輸出一個空行。
樣例輸入
5 4
XXXXX
X X
XXX X
XXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0
樣例輸出
Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.
深搜代碼
#include <bits/stdc++.h>
using namespace std;
struct point{int x,y,//出發行列 d,//方向 num;//線段數
};
bool k[100][100];//標記是不是牌，
int r,c,//地圖行列 sx,sy,tx,ty, //始發和終點位置 d[4][2]={{0,-1},{-1,0},{0,1},{1,0}},//左上右下四個方向的行列變化 num[100][100];//每個點四個方向的最少線段數,要逐個逐方向更新更小值。
void view(bool k[][100]){cout<<"地圖\n";cout<<" 列\t";for(int j=0;j<=c+1;j++)cout<<j<<"";cout<<endl;for(int i=0;i<=r+1;i++){cout<<i<<"行\t";for(int j=0;j<=c+1;j++)cout<<(k[i][j]?'X':' ')<<"";cout<<endl;}
}
void view(int k[][100],int ans){cout<<"最少線段數"<<ans<<endl;cout<<" 列\t";for(int j=0;j<=c+1;j++)cout<<j<<"";cout<<endl;for(int i=0;i<=r+1;i++){cout<<i<<"行\t";for(int j=0;j<=c+1;j++)cout<<num[i][j]<<"";cout<<endl;}cout<<endl;
}
void go(int x,int y,int f,int numx,int& ans){int x2,y2;for(int i=0;i<4;i++){x2=x+d[i][0],y2=y+d[i][1];if(x2<0||x2>r+1||y2<0||y2>c+1)continue;//不能越界 int cost=(i==f?numx:numx+1);if(cost>=ans)continue;//剪枝，超過最少線段數的線路不用考慮 if(x2==tx&&y2==ty){ans=min(ans,cost);//cout<<"OK"<<endl;view(num,ans);return;}if(k[x2][y2]||num[x2][y2])continue;//如果是牌不能穿越 num[x2][y2]=cost;//標記，并記住步數go(x2,y2,i,cost,ans); num[x2][y2]=0;//回溯 }
}
int main(){//freopen("data.cpp","r",stdin);int t1=1;while(cin>>c>>r&&(r||c)){//多組地圖，全部是0才結束 cin.get();//消融行結束標記 memset(k,0,sizeof(k));//初始化整個地圖,0是可以走 char cx;//地圖字符 for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cx=cin.get();k[i][j]=(cx=='X'?1:0);//卡片不能走 }cin.get();//消融行結束標記}cout<<"Board #"<<t1++<<":\n";//輸出組信息int t2=1,x,y,//出發行列 x2,y2;//到達行列 while(cin>>sy>>sx>>ty>>tx&&(sx||sy||tx||ty)){//多組數據，全部是0才結束 //cout<<"出發："<<sx<<","<<sy<<"\t"<<tx<<","<<ty<<endl;memset(num,0,sizeof(num));//各點初始化為最大值 int ans=0x3f3f3f;//0x3f=63,不夠大，0x3f3f3f=4194303夠了//view(k);go(sx,sy,-1,0,ans);cout<<"Pair "<<t2++<<": ";if(ans==0x3f3f3f)cout<<"impossible.\n";else cout<<ans<<" segments.\n"; }cout<<endl;//每組地圖后有空行 } return 0;
}
寬搜代碼
#include <bits/stdc++.h>
using namespace std;
struct point{int x,y,//出發行列 d,//方向 num;//線段數
};
bool k[100][100];//標記是不是牌，
int r,c,//地圖行列 sx,sy,tx,ty, //始發和終點位置 d[4][2]={{0,-1},{-1,0},{0,1},{1,0}},//左上右下四個方向的行列變化 num[100][100][4];//每個點四個方向的最少線段數,要逐個逐方向更新更小值。
int main(){//freopen("data2.cpp","r",stdin);int t1=1;while(cin>>c>>r&&(r||c)){//多組地圖，全部是0才結束 cin.get();//消融行結束標記 memset(k,0,sizeof(k));//初始化整個地圖,0是可以走 char cx;//地圖字符 for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cx=cin.get();if(cx=='X')k[i][j]=1;//k[i][j]=(cx=='X'?1:0);//卡片不能走 }cin.get();//消融行結束標記}cout<<"Board #"<<t1++<<":\n";//輸出組信息int t2=1,x,y,//出發行列 x2,y2;//到達行列 while(cin>>sy>>sx>>ty>>tx&&(sx||sy||tx||ty)){//多組數據，全部是0才結束 memset(num,0x3f3f3f,sizeof(num));//各點初始化為最大值 queue<point> q;//寬搜隊列 q.push(point{sx,sy,-1,0});//出發，下次方向都算不同，就會0+1多個線路for(int i=0;i<4;i++)num[sx][sy][i]=0;//出發位置各方向無線段 int ans=0x3f3f3f,//找最少線段數 cost;//中間值，存線段數變化結果 while(!q.empty()){point p=q.front();q.pop();x=p.x,y=p.y;for(int i=0;i<4;i++){//四個方向逐個嘗試 x2=x+d[i][0],y2=y+d[i][1];if(x2<0||x2>r+1||y2<0||y2>c+1)continue;//出界 cost=(p.d==i?p.num:p.num+1);//方向一樣線段數不變，否則多條線段 if(x2==tx&&y2==ty){//到達目標 if(num[x2][y2][i]>cost)num[x2][y2][i]=cost;ans=min(ans,cost);//更新最終最少線段數 }if(k[x2][y2])continue;//不能穿越牌if(num[x2][y2][i]>cost){//更少的線段數才更新并出發。 num[x2][y2][i]=cost;//更新該點i方向上的最少線段數 q.push(point{x2,y2,i,cost});//從新達點出發 }}}cout<<"Pair "<<t2++<<": ";if(ans==0x3f3f3f)cout<<"impossible.\n";else cout<<ans<<" segments.\n"; }cout<<endl;//每組地圖后有空行 } return 0;
}
深搜數據
地圖列 01234567
0行
1行 XXXX
2行 XX
3行 XX X
4行 XXX X
5行
Board #1:
出發：3,1 4,6
地圖列 01234567
0行
1行 XXXX
2行 XX
3行 XX X
4行 XXX X
5行
OK
最少線段數10列 01234567
0行 23333333
1行 20000054
2行 20000067
3行 10000098
4行 00000000
5行 00000000OK
最少線段數9列 01234567
0行 23333333
1行 20000054
2行 20000067
3行 10000008
4行 00000008
5行 00000000OK
最少線段數6列 01234567
0行 23333333
1行 20000054
2行 20000060
3行 10000060
4行 00000000
5行 00000000OK
最少線段數5列 01234567
0行 23333333
1行 20000004
2行 20000004
3行 10000004
4行 00000004
5行 00000000OK
最少線段數4列 01234567
0行 23333330
1行 20000040
2行 20000040
3行 10000040
4行 00000000
5行 00000000OK
最少線段數3列 01234567
0行 01222220
1行 01000030
2行 01000030
3行 00000030
4行 00000000
5行 00000000Pair 1: 3 segments.
演示圖
總結
1.問的不是步數，而是線段數
2.出發到到達方向一樣，是一條線段，
不一樣是兩條線段
所以出發位置得帶方向
3.寬搜，從不同方向到達該點，用更少線段數更新。不少不更新
例：短距離多線段，上2右1下1右1下1左2可達目標，是6線段
長距離少線段，上2右2下2左2，是4線段
4.數組得初始化。
如果用字符數組表示地圖，外延得初始化，否則有可能是’X’，不能通過。
5.從大開始找最小，
初始化整型數組(各點最少線段數num[100][100][4])，可以用 memset(num,0X3f3f3f,sizeof(num))
十六進制0X3f=整數63，不夠大.
十六進制0X3f3f3f=整數4194303.
再大就得逐一賦值。
6.深搜就是嘗試所有的情況，關鍵就是剪
