成都建设局官方网站,怎么做好网站建设,网站设计 现在流行的导航方式,企业网站建设合同书标准版马蹄印
题目大意#xff1a;
有一个只含括号的图#xff0c;要你走一条路#xff08;从左上角出发#xff09;#xff0c;使你走的路上的括号加在一起是先k个左括号再k个右括号组成的#xff0c;要求k最大
原题#xff1a;
题目描述#xff1a;
虽然当奶牛贝里斯找…马蹄印
题目大意
有一个只含括号的图要你走一条路从左上角出发使你走的路上的括号加在一起是先k个左括号再k个右括号组成的要求k最大
原题
题目描述
虽然当奶牛贝里斯找到平衡序列后很高兴了但是他现在对序列提出了一个更高的要求就是要求每个序列中必须是先一定数量的左括号然后是与左括号相同数量的右括号。例如就是一个完美的平衡序列。 当贝里斯某天在农场上走的时候他在地上发现了马蹄印这个农场是一个N*N的方格每个小方格中都有一个马蹄印。贝里斯希望从方格的最左上角的地方开始出发然后每次可以向上或者向下或者向左或者向右移动一步使得他走过的每个小方格中的马蹄印能够组成一个完美的平衡序列。当然了贝里斯不能重复经过任何小方格。
问题描述
请帮助贝里斯在这个N*N的方格中找出长度最长的完美序列的长度。
输入
第一行一个正整数N表示农场的大小。 接下来N行每行N个字符表示N*N的方格上马蹄印的分布情况。
输出
只有一行一个整数表示最长的完美序列的长度如果不存在这样的完美序列例如起始位置就是右括号则输出0。
输入样例
4
(())
()((
(()(
)))) 输出样例
8说明
数据范围2N5。 说明样例中奶牛的行走序列是这样的
1())
2)((
345(
876)解题思路
因为数据太小所以直接DFS就可以了
代码
#includecstdio
#includestring
#includecstring
#includeiostream
using namespace std;
int n,ans,p[10][10];
char a[10][10];
string str;
const int dx[4]{0,-1,0,1};
const int dy[4]{1,0,-1,0};
bool check(int xx,int yy)
{if (xx0xxnyy0yyn!p[xx][yy]) return true;//判断是否没出界没到过return false;
}
void dfs (int x,int y,int l,int r)
{if (lr){ansmax(ans,lr);//已经走完了return;}for (int i0;i4;i)if (check(xdx[i],ydy[i])){p[xdx[i]][ydy[i]]1;if (a[xdx[i]][ydy[i]](!r)//要没有走过右括号dfs(xdx[i],ydy[i],l1,r);if (a[xdx[i]][ydy[i]]))dfs(xdx[i],ydy[i],l,r1);p[xdx[i]][ydy[i]]0;//清零}
}
int main()
{scanf(%d,n);getchar();for (int i1;in;i){cinstr;for (int j1;jn;j)a[i][j]str[j-1];//读入}p[1][1]1;//初值if (a[1][1])) putchar(48);else dfs(1,1,1,0),printf(%d,ans);//输出
}
