首页 > 应用开发 > > ACM 关于F. XorPath问题
自己做的方法:
但是运行出错,不知道是不是递归产生的问题还是?
特此把代码放上来:
1 // XorPath.cpp : 定义控制台应用程序的入口点。
2 //
3
4 #include "stdafx.h"
5 #include <vector>
6 using std::vector;
7 #include <iostream>
8 using std::cout;
9 using std::cin;
10 using std::endl;
11 #include <iomanip>
12 using std::setw;
13
14 int row = 0, col = 0;
15 int paths = 0;
16 int n,m,k;
17 int *table =nullptr; //指向矩阵的全局指针
18
19
20 enum class dir{r,d};
21 dir flag;
22
23 struct rec{
24 int row,
25 col,
26 value;
27 };
28
29 vector<rec> mypath;
30
31 void xor_path()
32 {
33 int xor_sum = 0;
34 if (mypath.empty()) return;
35 else if (mypath.size()<2) xor_sum = mypath.back().value;
36 else
37 {
38 xor_sum = mypath.at(0).value ;
39 for (auto i = 1; i<mypath.size(); i++)
40 {
41 xor_sum ^= mypath.at(i).value ;
42 }
43 }
44
45 if (xor_sum == k) paths++; //若满足条件则计数
46 }
47
48 bool enable_forward()
49 {
50 if(col<n-1) //右移有效
51 {
52 flag = dir::r;
53 return true;
54 }
55 else if(row<m-1) //下移有效
56 {
57 flag = dir::d;
58 return true;
59 }
60 else
61 return false;
62 }
63
64 //当out_ctrl为真时则为外部控制前进方向,enable_forward()函数就不发挥作用
65 //默认由函数自主判断是否前进
66 void forward(bool out_ctrl=false)
67 {
68 rec temp;
69 if (out_ctrl) //外部控制只前进一步
70 {
71 switch(flag)
72 {
73 case dir::r:
74 col+=1;
75 break;
76 case dir::d:
77 row+=1;
78 break;
79 }
80 temp.row=row;temp.col=col;temp.value=table[row*m+col];
81 mypath.push_back(temp);
82 return;
83 }
84
85 while(enable_forward()) //只要可以前进,就一直前进
86 {
87 switch(flag) //每次前进一格,将该方格记录到mypath中
88 {
89 case dir::r:
90 col+=1;
91 break;
92 case dir::d:
93 row+=1;
94 break;
95 }
96 temp.row=row;temp.col=col;temp.value=table[row*m+col];
97 mypath.push_back(temp);
98 }
99 //无法前进即意味着到达终点(n,m)
100 //开始计算结果
101 xor_path();
102 }
103
104 void forward_down() //向下移动
105 {
106 flag = dir::d;
107 forward(true);
108 }
109
110 void forward_right() //向右移动
111 {
112 flag = dir::r;
113 forward(true);
114 }
115
116 void back()
117 {
118 rec pop;
119 do{
120 pop = mypath.back();
121 mypath.pop_back();
122 }while(mypath.back().col == pop.col);
123 //只要路径尾端和弹出数据在同一列则一直弹出
124
125 //重定位
126 row = mypath.back().row;
127 col = mypath.back().col;
128
129 //若路径为最后一行则一直后退
130 if (row == n-1) back();
131 }
132
133 void explore()
134 {
135 forward();
136 back();
137
138 if (!mypath.empty())
139 {
140 forward_down();
141 explore();
142 }
143 }
144
145 int _tmain(int argc, _TCHAR* argv[])
146 {
147 cout <<"请输入n,m,k:"<<endl;
148 cin >>n >>m >>k;
149
150 int b[]={2,1,5,7,10,0,12,6,4};
151 table = b; //将该矩阵传递到全局
152 /*
153 for( auto i = 0; i < n; i++)
154 {
155 cout << "row " <<i+1<<":"<<endl;
156 for (auto j = 0; j < m; j++)
157 {
158 cin >>*(a+i*m+j);
159
160 }
161 }
162 */
163 //显示输入的数据
164 cout << "data list:"<<endl;
165 for(auto t = 0; t< n*m; t++)
166 {
167 cout <<setw(5)<<table[t];
168 if ((t+1)%m == 0) cout<<endl;
169 }
170
171
172
173 //初始化路径起点
174 cout <<"初始化路径起点..."<<endl;
175 rec first ={0,0,*b};
176 mypath.push_back(first);
177 cout<<"first value= "<< mypath.at(0).value<<endl;
178
179 cout <<"exploring..." <<endl;
180 explore();
181 cout <<"output:paths= " << paths<<endl;
182 system("pasue");
183 return 0;
184 }//总是提示stack overflow...
//不管矩阵大小,都会提示溢出,郁闷ing
现在错误提示总是在vector上
说下标越界Line:159<vector> iterator +offset out of range.
....
来自 “ ITPUB博客 ” ,链接:https://blog.itpub.net/4605/viewspace-3154918/ ,如需转载,请注明出处,否则将追究法律责任。