제출 #1340751

#제출 시각아이디문제언어결과실행 시간메모리
1340751rony_jsPet (COCI26_pet)C++20
35 / 110
1094 ms608 KiB
#include <bits/stdc++.h>
#define int long long


using namespace std;


vector<vector<char>>graph;
int n,m;
int ans = 0;

inline void dfs(pair<int,int>idx, map<pair<int,int>,bool>vis, int c, char d){
	
	vis[idx]=1;

	if(c==5){ans++;return;}
	
		
	int x = idx.first, y = idx.second;

	if(d == 'i'){
		for(int i = 0; i<n; i++){
			if(graph[i][y]=='1' && i!=x){
				dfs({i,y},vis,c+1,'f');	
			}
		}
		for(int i = 0; i<m; i++){
			if(graph[x][i]=='1' && i!=y){
				dfs({x,i},vis,c+1,'c');
			}
		}
	}

	if(d == 'f'){
		for(int i = 0; i<m; i++){
			if(graph[x][i]=='1' && !vis[{x,i}]){
				dfs({x,i},vis,c+1,'c');
			}
		}
	}

	if(d=='c'){
		for(int i = 0; i<n; i++){
			if(graph[i][y]=='1' && !vis[{i,y}]){
				dfs({i,y},vis,c+1,'f');
			}
		}
	}

}

inline void solve(){

	cin>>n>>m;
	graph.resize(n,vector<char>(m));
	for(int i = 0; i<n; i++){
		for(int j = 0; j<m; j++){
			cin>>graph[i][j];
		}
	}
	int c = 1;
	map<pair<int,int>,bool>m1;
	for(int i = 0; i<n; i++){
		for(int j = 0; j<m; j++){
			if(graph[i][j]=='1')dfs({i,j},m1,c,'i');
		}
	}

	cout<<ans<<endl;

}


signed main(){

	solve();

	return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...