Hi
I'm currently working on Rotating Rings
https://www.spoj.pl/problems/ANARC07C/
at first, I received a runtime error (I use Dev C++) when I declared an array of size 1000x1000, I solved the problem on my compiler by declaring the array globally.
The code works just fine on my end, I even tried it with many test cases I designed (up to 8x8), but when I submitted the solution I received a RE (SIGSEGV), which translates to "Invalid memory reference" (Wikipedia).
I suspect it's the same error I encountered originally on Dev C++, but I'm not sure.
Any suggestions about the cause of the error greatly appreciated.
PS: I could post the code if needed (and if it's not against the forum rules), I made sure it's easy to understand and supplied comments where necessary.
Here's the code, as I said, it works fine with the test cases I made, but it's kinda hard to make a test case with size 1000x1000,
anyway, every function is tested and the test codes can be found among the comments, thanks for your time
#include<iostream>
using namespace std;
int box[1000][1000];
/******Calculate Ring Number******/
int ringNo(int size, int r, int c)
{
if(size%2)
{
for(int i=1; i<=(size/2)+1; i++)
if((r==i)||(c==i)||(r==size-i+1)||(c==size-i+1))
return i;
}
else
for(int i=1; i<=size/2; i++)
if((r==i)||(c==i)||(r==size-i+1)||(c==size-i+1))
return i;
}
/*****Calculate Next Location in Ring*****/
void nextLoc(int size, int &r, int &c)
{
int loc=ringNo(size,r,c);
if(r==loc)
if(c!=size-loc+1) {c++; return;}
if(c==size-loc+1)
if(r!=size-loc+1) {r++; return;}
if(r==size-loc+1)
if(c!=loc) {c--; return;}
r--;
}
/*****Calculate Next Value in Ring*****/
int nextVal(int size, int crnt)
{
if(crnt==size*size) return --crnt;
int r, c;
if(crnt%size) c=crnt-(crnt/size)*size;
else c=size;
if(crnt%size) r=crnt/size+1;
else r=crnt/size;
int loc=ringNo(size,r,c);
if(r==loc)
if(c!=size-loc+1) return ++crnt;
if(c==size-loc+1)
if(r!=size-loc+1) return crnt+size;
if(r==size-loc+1)
if(c!=loc) return --crnt;
return crnt-size;
}
/***## Main ##***/
int main()
{
int size,r,c,dummy; cin >> size; int tst=0; bool srt;
int len , /*ring length*/
start; /*starting value of ring*/
/*while(size) {cin >> r >> c; cout << ringNo(size,r,c) << endl; cin >> size;} //test for ringNo() */
/*while(size) {cin >> r >> c; nextLoc(size,r,c); cout << r << " " << c << endl; cin >> size;} //test for nextLoc() */
while (size)
{
for(int i=1; i<=size; i++)
for(int j=1; j<=size; j++)
cin >> box[i][j];
cout << ++tst << ". ";
dummy=(size/2)+1;
if(size%2) /*boxes with odd size have inner ring with size of 1 */
{
srt=box[dummy][dummy]==(size*size+1)/2;
if(!srt){cout << "NO\n"; cin >> size; continue;}
}
for(int i=size/2; i>0; i--)
{
r=i; c=i; start=(i-1)*size+i;
len=4*(1+size-2*i); srt=false;
for(int k=0; k<len; k++){srt=box[r][c]==start; if(srt)break; nextLoc(size,r,c);} /*set r,c to location of starting value*/
if(!srt) break;
for(int j=1; j<size; j++)
{
nextLoc(size,r,c); start=nextVal(size,start);
srt=box[r][c]==start;
if(!srt) break;
}
if(!srt) break;
}
if(!srt) cout << "NO\n";
else cout << "YES\n";
cin >> size;
}
return 0;
}
