fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int Mod = 1e9+7;
  5. int n,m,k;
  6. vector<vector<int>>grid;
  7. using ll =  long long;
  8.  
  9.  
  10. void spreadZer(){
  11. 	queue<pair<int,int>>q;
  12. 	vector<vector<int>>dist(n+1,vector<int>(m+1,INT_MAX));
  13.  
  14. 	for(int i = 1;i<=n;i++){
  15. 		for(int j= 1;j<=m ;j++){
  16. 			if(grid[i][j]==0){
  17. 				q.emplace(i,j);
  18. 				dist[i][j]=0;
  19. 			}
  20. 		}
  21. 	}
  22.  
  23. 	vector<vector<int>>dirn = {{-1,0},{1,0},{0,-1},{0,1}};
  24.  
  25. 	while(!q.empty()){
  26. 		auto u= q.front();
  27. 		int x =  u.first;
  28. 		int y = u.second;
  29. 		q.pop();
  30.  
  31. 		for(auto v:dirn){
  32. 			int dx = v[0];
  33. 			int dy = v[1];
  34. 			int nx = x+dx;int ny = y+dy;
  35. 			if(nx>=1 && ny>=1 && nx<=n && ny<=m && dist[nx][ny] == INT_MAX){
  36.  
  37. 				dist[nx][ny]=dist[x][y]+1;
  38. 				if(dist[nx][ny]<=k)
  39. 				{
  40. 				grid[nx][ny]=0;
  41. 				q.emplace(nx,ny);
  42. 				}
  43. 			}
  44. 		}
  45. 	}
  46. }
  47. int countPaths(){
  48. 	vector<vector<ll>>dp(n+1,vector<ll>(m+1,0));
  49. 	if(grid[1][1] == 1)dp[1][1]=1;
  50.  
  51. 	for(int i = 1 ;i<=n ;i++){
  52. 		for(int j = 1 ; j<=m ;j++){
  53. 			if(i==1 && j==1 || grid[i][j] == 0)continue;
  54. 			dp[i][j] = dp[i-1][j]+dp[i][j-1];
  55. 		}
  56. 	}
  57. 	return dp[n][m];
  58. }
  59. int main() {
  60. 	//int n,m;
  61. 	cin>>n>>m>>k;
  62. 	grid.assign(n+1,vector<int>(m+1)); 
  63. 	//int pack[n][m]; 
  64. 	for(int i = 1 ; i <= n ;i++){
  65. 		for(int j = 1 ; j <= m ;j++){
  66. 			cin>>grid[i][j];
  67. 		}
  68. 	} 
  69.  
  70. 	spreadZer();
  71. 	cout<<countPaths()<<endl;
  72. 	return 0;
  73. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
2 2 0
1 0
1 1
stdout
copy 
1
https://ideone.com/C8faZl
language:
C++ (gcc 8.3)
created:
20 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!