https://www.luogu.com.cn/problem/P1739
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
//template<typename DataType>
//DataType qmi(DataType m, int k)
//{
// DataType res = 1, t = m;
// while (k)
// {
// if (k&1) res = res * t;
// t = t * t;
// k >>= 1;
// }
// return res;
//}
int qmi(int m, int k)
{
int res = 1, t = m;
while (k)
{
if (k&1) res = res * t;
t = t * t;
k >>= 1;
}
return res;
}
int read(){
int x = 0,f = 1;
char c = getchar();
while (c<'0'||c>'9') {
if (c=='-') {
f = -1;
}
c = getchar();
}
while (c>='0'&&c<='9') {
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
#define fi(a,b) for(int i = a; i < b; i++)
#define fie(a,b) for(int i = a; i <= b; i++)
#define fj(a,b) for(int j = a; j >= b; j--)
char map[10000][10000];
//bit数组表示的是行；
int total = 0;//总数:记录解的总数
int n,m;//输入的数，即N*N的格子，全局变量，搜索中要用
int found = 0;
int cnt = 0;
string key = "yizhong";
string ke1 = "0123456";
void out(){
for (int i = 0; i < n; i++) {
for (int j = 0; j< m ; j++) {
cout<<map[i][j];
}
cout<<endl;
}
cout<<endl;
}
//搜索与回溯主体
int dfs(int x,int y,int k,int type){
if (map[x][y] == key[k] || map[x][y] == ke1[k]) {//找到了
map[x][y] = '0'+k;//表示已经用过了
bool isFound = false;//没有任何一个是匹配的
found = 0;
if(y - 1 >= 0 && (type == 1 || type == 0))
if((found = dfs(x,y - 1,k+1 ,1)) == 0){//左
}
if(!isFound)
isFound = found;
//out();
if(y + 1 < m && (type == 2 || type == 0))
if((found = dfs(x,y + 1,k+1,2))==0){//右
found = 0;//表示一个
}
//out();
if(!isFound)
isFound = found;
if(x - 1 >= 0 && (type == 3 || type == 0))
if((found = dfs(x - 1,y,k+1,3))==0){
}
//out();
if(!isFound)
isFound = found;
if(x + 1 < n && (type == 4 || type == 0))
if((found = dfs(x + 1,y,k+1,4)) == 0){
}
//out();
if(!isFound)
isFound = found;
if(y - 1 >= 0 && x - 1 >= 0 && (type == 5 || type == 0))
if((found = dfs(x - 1,y - 1,k+1,5))==0){
}
//out();
if(!isFound)
isFound = found;
if(y - 1 >= 0 && x + 1 < n && (type == 6 || type == 0))
if((found = dfs(x + 1,y - 1,k+1,6)) == 0){
}
//out();
if(!isFound)
isFound = found;
if(y + 1 < m && x + 1 < n && (type == 7 || type == 0))
if((found = dfs(x + 1,y + 1,k+1,7)) == 0){
}
//out();
if(!isFound)
isFound = found;
if(y + 1 < m && x - 1 >= 0 && (type == 8 || type == 0))
if((found = dfs(x - 1,y + 1,k+1,8)) ==0){
}
if (!isFound && k!=6) {
if( k > 0 && map[x][y] != ke1[k])
map[x][y] = key[k];//没找到后续的
else if( k==0 )
map[x][y] = key[k];//没找到后续的
return 0;
}
return 1;//查找成功的
} else {
return 0;//查找失败的
}
}
queue<char>a;
int left,right,t;
void read(){
char ch = getchar();
while(ch!='@'){
a.push(ch);
ch = getchar();
}
}
int main(){
read();
while(!a.empty()){
if(a.front() == '('){
++ left;
++ t;
}
if(a.front()==')'){
++ right;
if(t){
-- t;
}
}
a.pop();
}
if(left==right&&t==0){
printf("YES");
} else {
printf("NO");
}
return 0;
}
/*
8
yyzhongy
iiihhiia
zhzzzzoa
hffhhssa
oooooooa
nnnnnnna
gggggggg
aaaaaaaa
============
3
*/
网友评论