正題

題目鏈接:https://jzoj.net/senior/#main/show/1404

---

題目大意

給出一個(gè)菱形中有一些邊，求有多少個(gè)中間沒有邊的平行四邊形。

---

解題思路

我們將一個(gè)平行四邊形拆成兩個(gè)等腰三角形和一個(gè)平行于菱形中間對(duì)角線的平行四邊形，我們可以判斷上面那個(gè)等腰三角形在判斷下面的。

---

$code$

#pragma GCC optimize("O2") #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int dx[8]={0,0,1,-1,1,-1,1,-1},dy[8]={1,-1,0,0,1,-1,-1,1}; const int N=1100; queue<int> qx,qy; int n,m,dis[N][N]; bool v[N][N]; char a[N][N]; void bfs() {while(!qx.empty()){int x=qx.front(),y=qy.front();v[x][y]=0;qx.pop();qy.pop();for(int k=0;k<8;k++){int zx=x+dx[k],zy=y+dy[k];if(zx<1||zy<1||zx>n||zy>n) continue;int w=(a[zx][zy]=='0')*(a[x][y]=='1');if(dis[x][y]+w<dis[zx][zy]){dis[zx][zy]=dis[x][y]+w;if(!v[zx][zy]){qx.push(zx);qy.push(zy);v[zx][zy]=1;}}}} } void try_add(int x,int y) {if(v[x][y]) return;v[x][y]=1;dis[x][y]=0;qx.push(x),qy.push(y);return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);memset(dis,0x3f,sizeof(dis));for(int i=1;i<=n;i++)try_add(1,i),try_add(i,1),try_add(n,i),try_add(i,n); bfs();for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);printf("%d ",dis[x][y]);} }

總結(jié)

以上是生活随笔為你收集整理的jzoj1404-菱形内的计数【模拟】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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