300iq Contest 3 C. Cells Blocking

Give me a picture‘ Represents open space and '*' represents obstacles. You can go right or down each time. Ask how many points are satisfied. After blocking the two open spaces, make it go from the upper left corner (1,1) to the lower right corner (n,m).

Problem solution: preprocess the points that can be reached from (1,1) and backward from (n,m), and delete other inaccessible open spaces (count the total number of open spaces before deleting). If you can't start from (1,1) to (n,m), get the answer directly.

Group these points according to their diagonal lines.

Obviously, if there is only one open space on a diagonal, the empty point can be combined with any open space to block the whole road. Directly count the number of points in this part.

If there are multiple open spaces on a diagonal. So if you want to block some of the open spaces. Only the two most marginal open spaces can be selected.

First of all, we ignore the case that there is only one open space on the diagonal, because the point pairs in this part have been counted.

For the remaining two diagonals, the two open spaces on the left and the two open spaces on the right must be connected, because they can only go to the right and down. For example, if you can't reach (5,2) from (3,1), then (3,1) must be able to reach (4,3) (or another space on the right). Then (5,2) must arrive from (2,2) to become an open space. And if (2,2) can reach (5,2), (3,1) can (their paths must have intersections).

Therefore, if there are three or more open spaces in a slash, only the left or right open space can be selected to block one or two of them. Block the middle point, no matter how blocked the back, at least from one of the open spaces at both ends to the end.

1,1 1,2 1,3 1,4 1,5
2,1 2,2 2,3 2,4 2,5
3,1 3,2 3,3 3,4 3,5
4,1 4,2 4,3 4,4 4,5
5,1 5,2 5,3 5,4 5,5

Assuming that the leftmost open space is blocked, we now want to enumerate which points of the lower right slash can make the path completely blocked.

Let's start from the two open spaces on the left and the far right of the slash. For the open space on the second left, if you can go down, go down as far as possible. Otherwise, go right. The open space on the far right. If you can go to the right, swim to it. If you play right down again, there will be a convergence in the process of walking. It shows that blocking the open space on the current slash can also block the whole road.

The code is 300iq:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
char c[3005][3005];
bool dp[3005][3005];
bool dp2[3005][3005];
vector<int>v[6005];
ll cnt=0,ans=0;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=m ;j++){
			cin >> c[i][j];
			dp[i][j]|=dp[i-1][j];
			dp[i][j]|=dp[i][j-1];
			dp[i][j]|=(i==1 && j==1);
			dp[i][j]&=(c[i][j]=='.');
			cnt+=(c[i][j]=='.');
		}
	}
	for(int i=n; i>=1 ;i--){
		for(int j=m; j>=1 ;j--){
			dp2[i][j]|=dp2[i+1][j];
			dp2[i][j]|=dp2[i][j+1];
			dp2[i][j]|=(i==n && j==m);
			dp2[i][j]&=(c[i][j]=='.');
		}
	}
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=m ;j++){
			if(!dp[i][j] || !dp2[i][j]) c[i][j]='*';
			else v[i+j].push_back(i);
		}
	}
	if(!dp[n][m]) return cout << cnt*(cnt-1)/2 << '\n',0;
	ll bh=0;
	for(int i=2; i<=n+m ;i++){
		if(v[i].size()==1) ans+=(cnt-(++bh));
	}
	for(int i=2; i<=n+m ;i++){
		if(v[i].size()==1) continue;
		int l=v[i][1],r=v[i].back();
		if(l==r) ans++;
		for(int j=i+1; j<=n+m ;j++){
			if(c[l][j-l]!='.') l++;
			if(c[r+1][j-r-1]=='.') r++;
			if(l==r && v[j].size()!=1) ans++;  
		}
	}
	for(int i=2; i<=n+m ;i++){
		if(v[i].size()==1) continue;
		int l=v[i][0],r=v[i][v[i].size()-2];
		for(int j=i+1; j<=n+m ;j++){
			if(c[l][j-l]!='.') l++;
			if(c[r+1][j-r-1]=='.') r++;
			if(l==r && v[j].size()!=1) ans++;  
		}
	}
	cout << ans << '\n';
}

Posted by primate on Tue, 03 May 2022 06:11:52 +0300