題目描述
Orz likes to play dominoes. Now giving an n*m chessboard and k dominoes whose size are 1*2, Orz finds that there is exactly one grid empty, so that he can move dominoes without overlapping them. An initial situation is given, he wants to know how many final situation could be achieved, except the initial situation. Note every domino is different, as they have their own serial number. Since the answer may be very large, please output the answer modulo 1000000009.?

輸入
There will be multiple test cases. For each test case:
The first line contains three integers: n, m, k(n ≤ 9, m ≤ 10000).
The following k lines, each line contains four integers: a? b? c? d, indicating that this domino occupies (a, b) and (c, d).?
The input guarantees that the domino does not overlap, and there is exactly one empty grid.

輸出
For each test cases, output the answer modulo 1000000009.

?

樣例輸入
5 5 12
1 1 2 1
1 2 2 2
1 3 2 3
1 4 1 5
2 4 2 5
3 4 3 5
3 1 3 2
4 1 4 2
5 1 5 2
4 3 5 3
4 4 5 4
4 5 5 5
樣例輸出
8

題意：類似華容道，問空格能在多少個位置出現

多米諾牌是1*2大小的，它可以橫著放，也可以豎著放。

題目給出了k個多米諾牌的兩個格子的坐標。

牌橫著放的時候兩個格子的橫坐標相等，記為1；豎著放的時候兩個格子的縱坐標相等，記為2。

空格可以上下左右四個方向移動：

如果空格能向上向下移動，那么，空格上下的牌必須是豎著放的；

如果空格能向左向右移動，那么，空格左右的牌必須是橫著放的。

首先判斷空格上下左右的牌是如何放置的，再判斷空格能否移動。

標記空格走過的位置，空格出現的位置的狀態是唯一的。

純bfs,一層一層的搜。

#include<algorithm> #include<iostream> #include<cstring> #include<queue> #include<cstdio> using namespace std; int MAP[15][10005],ans,vis[15][10005],n,m; int dir[4][2]= {-1,0,1,0,0,-1,0,1}; struct node {int x,y; }; queue<node>p; int judge(int x,int y) {if(x>=1&&x<=n&&y>=1&&y<=m)return 1;elsereturn 0; } void bfs_(int tx,int ty) {node q;q.x=tx,q.y=ty;p.push(q);//將空格的位置入隊列vis[tx][ty]=1;int sx,sy;while(!p.empty()){node temp;temp=p.front();p.pop();vis[temp.x][temp.y]=1;node L;sx = temp.x;sy = temp.y;if(MAP[sx-1][sy]==2&&judge(sx-2,sy)&&vis[sx-2][sy]==0)//空格上面的牌是豎著放的，牌只能向下移動{ //（sx-2,sy）是移動之后空格的坐標ans++;L.x=sx-2,L.y=sy;vis[sx-2][sy]=1;p.push(L);}if(MAP[sx+1][sy]==2&&judge(sx+2,sy)&&vis[sx+2][sy]==0)//空格下面的牌是豎著放的，牌只能向上移動 {ans++;L.x=sx+2,L.y=sy;vis[sx+2][sy]=1;p.push(L);}if(MAP[sx][sy-1]==1&&judge(sx,sy-2)&&vis[sx][sy-2]==0)//空格左邊的牌是橫著放的，牌只能向右移動 {ans++;L.x=sx,L.y=sy-2;vis[sx][sy-2]=1;p.push(L);}if(MAP[sx][sy+1]==1&&judge(sx,sy+2)&&vis[sx][sy+2]==0)//空格右邊的牌是橫著放的，牌只能向左移動 {ans++;L.x=sx,L.y=sy+2;vis[sx][sy+2]=1;p.push(L);}}} int main() {int k,tx,ty;while(~scanf("%d%d%d",&n,&m,&k)){int x1,y1,x2,y2;ans=0;memset(MAP,0,sizeof(MAP));memset(vis,0,sizeof(vis));for(int i=1; i<=k; i++){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);if(x1 == x2)MAP[x1][y1]=1,MAP[x2][y2]=1;elseMAP[x1][y1]=2,MAP[x2][y2]=2;}int flag = 0;for(int i=1; i<=n; i++) //找到空格的位置 {for(int j=1; j<=m; j++){if(MAP[i][j] == 0){tx=i,ty=j;flag = 1;break;}}if(flag)break;}bfs_(tx,ty);printf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/LLLAIH/p/10735135.html

總結

以上是生活随笔為你收集整理的6993: Dominoes（纯bfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。