廣度優(yōu)先搜索。注意題目中說(shuō)結(jié)果可能很大，但是實(shí)際上是到不了1e9+9的，有些題目就是故意嚇唬人。

代碼：

#include <iostream> ? //分開也是可以的吧。?
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
int map[11][10010];?? ??? ?//尋求蛛絲馬跡拼湊而成。?
const int mod=1000000009;
int z=90001;
struct node
{
?? ?int x,y;
?? ?char dir;
?? ?char flag;?
};

int main()
{
?? ?int n,m,k;
?? ?while(~scanf("%d %d %d",&n,&m,&k))
?? ?{
?? ?//?? ?z=90001;
?? ??? ?memset(map,0,sizeof(map)); ? ? ? ? ? ? ? ? ?
?? ??? ?int a,b,c,d;
?? ??? ?for(int i=1;i<=k;i++)?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?
?? ??? ?{
?? ??? ??? ?scanf("%d %d %d %d",&a,&b,&c,&d);
?? ??? ??? ?map[a][b]=i;
?? ??? ??? ?map[c][d]=i;?? ?
?? ??? ?}
?? ??? ?//之后進(jìn)行廣度優(yōu)先搜索。
?? ??? ?for(int i=1;i<=n;i++)
?? ??? ?{
?? ??? ??? ?for(int j=1;j<=m;j++)
?? ??? ??? ??? ?if(map[i][j]==0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?a=i;b=j;
?? ??? ??? ??? ??? ?c=-1;
?? ??? ??? ??? ??? ?break;?? ??? ??? ?
?? ??? ??? ??? ?}
?? ??? ??? ?if(c==-1)
?? ??? ??? ??? ?break;
?? ??? ?}?? ?
?? ??? ?node temp1;?? ? ?? ??? ??? ??
?? ??? ?temp1.x=a; ?temp1.y=b; temp1.dir ='O';?? ??? ??? ??? ??? ?
?? ??? ?queue<node>q;?? ??? ??? ? ?? ? ?//應(yīng)該是有條件限制的。 加上條件限制時(shí)候用最為笨的方法實(shí)現(xiàn)。?
?? ??? ?q.push(temp1);?? ??? ?
?? ??? ?ll ans=0;
?? ??? ?while( !q.empty() )
?? ??? ?{
?? ??? ??? ?node temp=q.front();
?? ??? ??? ?q.pop();?? ??? ??? ? ? ? ?//通過(guò)迷宮中的移動(dòng)方式應(yīng)該也是可以。
?? ??? ??? ?if(temp.dir =='O');?? ??? ? ?//首先的目的就是進(jìn)行移動(dòng)，這是第一步，之后還是有其它的方式。?? ?
?? ??? ??? ?else?? ??? ??? ??
?? ??? ??? ?{
?? ??? ??? ??? ?if(temp.dir=='U') ? ? //U,D,L,R; ?移動(dòng)錯(cuò)誤。?
?? ??? ??? ??? ??? ?map[temp.x+2][temp.y]=mod/*map[temp.x][temp.y]*/,map[temp.x][temp.y]=0;
?? ??? ??? ??? ?else if(temp.dir=='D')
?? ??? ??? ??? ??? ?map[temp.x-2][temp.y]=mod/*map[temp.x][temp.y]*/,map[temp.x][temp.y]=0;
?? ??? ??? ??? ?else if(temp.dir=='L')
?? ??? ??? ??? ??? ?map[temp.x][temp.y+2]=mod/*map[temp.x][temp.y]*/,map[temp.x][temp.y]=0; ? //先不進(jìn)行考慮。
?? ??? ??? ??? ?else if(temp.dir=='R')
?? ??? ??? ??? ??? ?map[temp.x][temp.y-2]=mod/*map[temp.x][temp.y]*/,map[temp.x][temp.y]=0;?
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?if( temp.x-2>=1&&map[temp.x-1][temp.y]==map[temp.x-2][temp.y] )?? ?
?? ??? ??? ?{
?? ??? ??? ??? ?ans=(ans+1)%mod;
?? ??? ??? ??? ?node temp2;
?? ??? ??? ??? ?temp2.dir='U',temp2.x=temp.x-2,temp2.y=temp.y;
?? ??? ??? ??? ?q.push(temp2);?? ?
?? ??? ??? ?}?? ??? ??? ??? ? ?
?? ??? ??? ?if(temp.x+2<=n&& map[temp.x+2][temp.y]==map[temp.x+1][temp.y] ) ?//對(duì)啊，這里是永遠(yuǎn)也是不能結(jié)束的。?
?? ??? ??? ?{
?? ??? ??? ??? ?ans=(ans+1)%mod;
?? ??? ??? ??? ?node temp4;
?? ??? ??? ??? ?temp4.dir='D',temp4.x=temp.x+2,temp4.y=temp.y;
?? ??? ??? ??? ?q.push(temp4);?? ?
?? ??? ??? ?} ?? ??? ??? ??? ?
?? ??? ??? ?if(temp.y-2>=1&& map[temp.x][temp.y-2]==map[temp.x][temp.y-1] )
?? ??? ??? ?{
?? ??? ??? ??? ?ans=(ans+1)%mod;
?? ??? ??? ??? ?node temp6;
?? ??? ??? ??? ?temp6.dir='L',temp6.x=temp.x,temp6.y=temp.y-2;
?? ??? ??? ??? ?q.push(temp6);?? ?
?? ??? ??? ?}?? ? ??? ??? ? ? ?? ?
?? ??? ??? ?if( ?temp.y+2<=m&&map[temp.x][temp.y+1]==map[temp.x][temp.y+2] )
?? ??? ??? ?{
?? ??? ??? ??? ?ans=(ans+1)%mod;
?? ??? ??? ??? ?node temp8;
?? ??? ??? ??? ?temp8.dir='R',temp8.x=temp.x,temp8.y=temp.y+2;
?? ??? ??? ??? ?q.push(temp8);
?? ??? ??? ?}?? ??? ??? ?
?? ??? ?}?
?? ??? ?cout<<ans<<endl;
?? ?}?? ?
?? ?return 0;
}

總結(jié)

以上是生活随笔為你收集整理的2018山东省省赛 问题 H: Dominoes的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。