贵有恒，何必三更起五更眠；最无益，莫过一日曝十日寒。
6993: Dominoes
时间限制: 1 Sec 内存限制: 128 MB
提交: 45 解决: 20
[提交][状态][讨论版][命题人:admin]
题目描述
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
题意：有一块拼图板，n行，m列。上面有k块2*1的拼图。这些拼图是可以移动的。但这个拼图上有一个空的1*1的格子。这样使得
空格附近的拼图是可以移动的。所以经过移动，可以移动出很多种不同的拼图形状。问最终的结果数目：
思路：采用广度优先搜索，我们用1和2来代表一个拼图的状态。1代表横向的，2代表竖向的。这样，一个空格子上方的拼图如果是竖着的，则这个拼图可以向下移动，同理推得其他方向拼图可移动方向。拼图移动后，势必会产生一个新的空格子，再对此空格子进行讨论，直到广搜结束。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define M(a,b) memset(a,b,sizeof(a))
const int MAXN = 1e4+5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000009;
int n,m,k;
int x11,x22,y11,y22;
int sx,sy;
int MAP[15][10005];
struct Node
{int x,y;
};
int vis[15][10005];///标记访问情况
queue<Node>q;
bool check(int x3,int y3)
{if(x3>=1&&y3>=1&&x3<=n&&y3<=m){return true;}return false;
}
int bfs(int x,int y)
{int ans=0;Node temp;temp.x = x;temp.y = y;vis[x][y] = 1;q.push(temp);while(!q.empty()){Node TOP = q.front();q.pop();int xx = TOP.x;int yy = TOP.y;if(MAP[xx-1][yy]==2&&check(xx-2,yy)&&vis[xx-2][yy]==0)///下方的格子可以上移，空格子坐标更新为(xx-2,yy),并入队列{ans++;vis[xx-2][yy] = 1;///访问情况更新Node temp2;temp2.x = xx-2;temp2.y = yy;q.push(temp2);}if(MAP[xx+1][yy]==2&&check(xx+2,yy)&&vis[xx+2][yy]==0)///上方的格子可以下移，空格子坐标更新为(xx+2,yy),并入队列{ans++;vis[xx+2][yy] = 1;Node temp2;temp2.x = xx+2;temp2.y = yy;q.push(temp2);}if(MAP[xx][yy-1]==1&&check(xx,yy-2)&&vis[xx][yy-2]==0)///左方的格子可以右移，空格子坐标更新为(xx,yy-2),并入队列{ans++;vis[xx][yy-2] = 1;Node temp2;temp2.x = xx;temp2.y = yy-2;q.push(temp2);}if(MAP[xx][yy+1]==1&&check(xx,yy+2)&&vis[xx][yy+2]==0)///右方的格子可以左移，空格子坐标更新为(xx,yy+2),并入队列{ans++;vis[xx][yy+2] = 1;Node temp2;temp2.x = xx;temp2.y = yy+2;q.push(temp2);}}return ans;
}
int main()
{while(~scanf("%d%d%d",&n,&m,&k)){M(vis,0);M(MAP,0);while(!q.empty()) q.pop();for(int i=0; i<k; i++){scanf("%d %d %d %d",&x11,&y11,&x22,&y22);if(x11==x22)///x11和x22相等说明该拼图是横着的{MAP[x11][y11] = 1;///1带表横着的MAP[x22][y22] = 1;}else{MAP[x11][y11] = 2;///2带表竖着的MAP[x22][y22] = 2;}}int flag = 0;for(int i=1; i<=n; i++)///确定初始空格子的位置{for(int j=1; j<=m; j++){if(MAP[i][j]==0){flag = 1;sx = i;sy = j;break;}}if(flag) break;}int ans = bfs(sx,sy);printf("%d\n",ans%MOD);}return 0;
}