#include<iostream>
using namespace std;
int main() {
// 0 empty, 1 = x, 2 = o
int grid[100][100] = { 0 };
int n;
cout<<"Enter grid dimension: ";
cin >> n;
/*
We can write length code to verify N row, N columns and 2 diagonals
Notice: the behavior of all of them is SAME
E.g. We have some starting point (e.g. 0 0) and we need to verify its row
We can use a direction-array style to write an elegant code
We will create a single array with the (2N+2) needed verifications
For every verification we need 4 values:
The starting point (r, c): we need the starting of each row (N), col (N), 2 Diagonals
The direction to move in it for N steps
For example, for the starting (0, 0)
To verify its row, we need direction (1, 0)
To verify its col, we need direction (0, 1)
To verify its diagonal, we need direction (1, 1)
To verify the right diagonal: we start from the last cell in first row (0, n-1) and moves (1, -1)
1 means move to next row. -1 means move to the previous column
Once done: we iterate over all such start/direction.
Loop n times to verify they all same play symbol
*/
int rs[100], cs[100], dr[100], dc[100];
int verify = 0;
// Add row n positions to verify
for (int r = 0; r < n; ++r)
rs[verify] = r, cs[verify] = 0, dr[verify] = 0, dc[verify++] = 1;
// Add col n positions to verify
for (int c = 0; c < n; ++c)
rs[verify] = 0, cs[verify] = c, dr[verify] = 1, dc[verify++] = 0;
// Add diagonal 1
rs[verify] = 0, cs[verify] = 0, dr[verify] = 1, dc[verify++] = 1;
// Add diagonal 2
rs[verify] = 0, cs[verify] = n - 1, dr[verify] = 1, dc[verify++] = -1;
int turn = 0; // 0 for x, 1 for o. Don't get confused with grid values
int steps = 0;
while (true) {
if (steps == n*n) {
cout<<"Tie\n";
break;
}
char symbol = 'x';
if (turn == 1)
symbol = 'o';
cout << "Player " << symbol << " turn. Enter empty location (r, c): ";
int r, c;
cin >> r >> c;
r--, c--;
if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 0) {
cout << "Invalid input. Try again\n";
continue;
}
grid[r][c] = turn + 1;
// print the grid
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
char ch = '.';
if (grid[r][c] == 1)
ch = 'x';
else if (grid[r][c] == 2)
ch = 'o';
cout << ch;
}
cout << "\n";
}
// Check win status
for (int check = 0; check < verify; ++check) {
int r = rs[check], c = cs[check], rd = dr[check], cd = dc[check];
int cnt = 0, first = grid[r][c];
if (first == 0)
continue;
for (int step = 0; step < n; ++step, r += rd, c += cd)
cnt += grid[r][c] == first;
if (cnt == n) {
cout << "Player " << symbol << " won\n";
return 0;
}
}
turn = !turn; // 0 be 1, 1 be 0 = flip player
steps++;
}
return 0;
}
/*
For tie
3
1 1
1 3
1 2
2 2
3 2
2 1
2 3
3 3
3 1
*/
I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCS8vIDAgZW1wdHksIDEgPSB4LCAyID0gbwoJaW50IGdyaWRbMTAwXVsxMDBdID0geyAwIH07CgoJaW50IG47Cgljb3V0PDwiRW50ZXIgZ3JpZCBkaW1lbnNpb246ICI7CgljaW4gPj4gbjsKCgkvKgoJCVdlIGNhbiB3cml0ZSBsZW5ndGggY29kZSB0byB2ZXJpZnkgTiByb3csIE4gY29sdW1ucyBhbmQgMiBkaWFnb25hbHMKCgkJTm90aWNlOiB0aGUgYmVoYXZpb3Igb2YgYWxsIG9mIHRoZW0gaXMgU0FNRQoJCQlFLmcuIFdlIGhhdmUgc29tZSBzdGFydGluZyBwb2ludCAoZS5nLiAwIDApIGFuZCB3ZSBuZWVkIHRvIHZlcmlmeSBpdHMgcm93CgoJCVdlIGNhbiB1c2UgYSBkaXJlY3Rpb24tYXJyYXkgc3R5bGUgdG8gd3JpdGUgYW4gZWxlZ2FudCBjb2RlCgoJCVdlIHdpbGwgY3JlYXRlIGEgc2luZ2xlIGFycmF5IHdpdGggdGhlICgyTisyKSBuZWVkZWQgdmVyaWZpY2F0aW9ucwoJCUZvciBldmVyeSB2ZXJpZmljYXRpb24gd2UgbmVlZCA0IHZhbHVlczoKCQkJVGhlIHN0YXJ0aW5nIHBvaW50IChyLCBjKTogd2UgbmVlZCB0aGUgc3RhcnRpbmcgb2YgZWFjaCByb3cgKE4pLCBjb2wgKE4pLCAyIERpYWdvbmFscwoJCQlUaGUgZGlyZWN0aW9uIHRvIG1vdmUgaW4gaXQgZm9yIE4gc3RlcHMKCgkJRm9yIGV4YW1wbGUsIGZvciB0aGUgc3RhcnRpbmcgKDAsIDApCgkJCVRvIHZlcmlmeSBpdHMgcm93LCB3ZSBuZWVkIGRpcmVjdGlvbiAoMSwgMCkKCQkJVG8gdmVyaWZ5IGl0cyBjb2wsIHdlIG5lZWQgZGlyZWN0aW9uICgwLCAxKQoJCQlUbyB2ZXJpZnkgaXRzIGRpYWdvbmFsLCB3ZSBuZWVkIGRpcmVjdGlvbiAoMSwgMSkKCQlUbyB2ZXJpZnkgdGhlIHJpZ2h0IGRpYWdvbmFsOiB3ZSBzdGFydCBmcm9tIHRoZSBsYXN0IGNlbGwgaW4gZmlyc3Qgcm93ICgwLCBuLTEpIGFuZCBtb3ZlcyAoMSwgLTEpCgkJCTEgbWVhbnMgbW92ZSB0byBuZXh0IHJvdy4gLTEgbWVhbnMgbW92ZSB0byB0aGUgcHJldmlvdXMgY29sdW1uCgoJCU9uY2UgZG9uZTogd2UgaXRlcmF0ZSBvdmVyIGFsbCBzdWNoIHN0YXJ0L2RpcmVjdGlvbi4KCQkJTG9vcCBuIHRpbWVzIHRvIHZlcmlmeSB0aGV5IGFsbCBzYW1lIHBsYXkgc3ltYm9sCgkgKi8KCglpbnQgcnNbMTAwXSwgY3NbMTAwXSwgZHJbMTAwXSwgZGNbMTAwXTsKCglpbnQgdmVyaWZ5ID0gMDsKCgkvLyBBZGQgcm93IG4gcG9zaXRpb25zIHRvIHZlcmlmeQoJZm9yIChpbnQgciA9IDA7IHIgPCBuOyArK3IpCgkJcnNbdmVyaWZ5XSA9IHIsIGNzW3ZlcmlmeV0gPSAwLCBkclt2ZXJpZnldID0gMCwgZGNbdmVyaWZ5KytdID0gMTsKCgkvLyBBZGQgY29sIG4gcG9zaXRpb25zIHRvIHZlcmlmeQoJZm9yIChpbnQgYyA9IDA7IGMgPCBuOyArK2MpCgkJcnNbdmVyaWZ5XSA9IDAsIGNzW3ZlcmlmeV0gPSBjLCBkclt2ZXJpZnldID0gMSwgZGNbdmVyaWZ5KytdID0gMDsKCgkvLyBBZGQgZGlhZ29uYWwgMQoJcnNbdmVyaWZ5XSA9IDAsIGNzW3ZlcmlmeV0gPSAwLCBkclt2ZXJpZnldID0gMSwgZGNbdmVyaWZ5KytdID0gMTsKCS8vIEFkZCBkaWFnb25hbCAyCglyc1t2ZXJpZnldID0gMCwgY3NbdmVyaWZ5XSA9IG4gLSAxLCBkclt2ZXJpZnldID0gMSwgZGNbdmVyaWZ5KytdID0gLTE7CgoJaW50IHR1cm4gPSAwOwkvLyAwIGZvciB4LCAxIGZvciBvLiBEb24ndCBnZXQgY29uZnVzZWQgd2l0aCBncmlkIHZhbHVlcwoKCWludCBzdGVwcyA9IDA7Cgl3aGlsZSAodHJ1ZSkgewoJCWlmIChzdGVwcyA9PSBuKm4pIHsKCQkJY291dDw8IlRpZVxuIjsKCQkJYnJlYWs7CgkJfQoJCWNoYXIgc3ltYm9sID0gJ3gnOwoJCWlmICh0dXJuID09IDEpCgkJCXN5bWJvbCA9ICdvJzsKCgkJY291dCA8PCAiUGxheWVyICIgPDwgc3ltYm9sIDw8ICIgdHVybi4gRW50ZXIgZW1wdHkgbG9jYXRpb24gKHIsIGMpOiAiOwoJCWludCByLCBjOwoJCWNpbiA+PiByID4+IGM7CgoJCXItLSwgYy0tOwoKCQlpZiAociA8IDAgfHwgciA+PSBuIHx8IGMgPCAwIHx8IGMgPj0gbiB8fCBncmlkW3JdW2NdICE9IDApIHsKCQkJY291dCA8PCAiSW52YWxpZCBpbnB1dC4gVHJ5IGFnYWluXG4iOwoJCQljb250aW51ZTsKCQl9CgkJZ3JpZFtyXVtjXSA9IHR1cm4gKyAxOwoKCQkvLyBwcmludCB0aGUgZ3JpZAoJCWZvciAoaW50IHIgPSAwOyByIDwgbjsgKytyKSB7CgkJCWZvciAoaW50IGMgPSAwOyBjIDwgbjsgKytjKSB7CgkJCQljaGFyIGNoID0gJy4nOwoJCQkJaWYgKGdyaWRbcl1bY10gPT0gMSkKCQkJCQljaCA9ICd4JzsKCQkJCWVsc2UgaWYgKGdyaWRbcl1bY10gPT0gMikKCQkJCQljaCA9ICdvJzsKCQkJCWNvdXQgPDwgY2g7CgkJCX0KCQkJY291dCA8PCAiXG4iOwoJCX0KCgkJLy8gQ2hlY2sgd2luIHN0YXR1cwoJCWZvciAoaW50IGNoZWNrID0gMDsgY2hlY2sgPCB2ZXJpZnk7ICsrY2hlY2spIHsKCQkJaW50IHIgPSByc1tjaGVja10sIGMgPSBjc1tjaGVja10sIHJkID0gZHJbY2hlY2tdLCBjZCA9IGRjW2NoZWNrXTsKCQkJaW50IGNudCA9IDAsIGZpcnN0ID0gZ3JpZFtyXVtjXTsKCgkJCWlmIChmaXJzdCA9PSAwKQoJCQkJY29udGludWU7CgoJCQlmb3IgKGludCBzdGVwID0gMDsgc3RlcCA8IG47ICsrc3RlcCwgciArPSByZCwgYyArPSBjZCkKCQkJCWNudCArPSBncmlkW3JdW2NdID09IGZpcnN0OwoKCQkJaWYgKGNudCA9PSBuKSB7CgkJCQljb3V0IDw8ICJQbGF5ZXIgIiA8PCBzeW1ib2wgPDwgIiB3b25cbiI7CgkJCQlyZXR1cm4gMDsKCQkJfQoJCX0KCgkJdHVybiA9ICF0dXJuOwkvLyAwIGJlIDEsIDEgYmUgMCA9IGZsaXAgcGxheWVyCgkJc3RlcHMrKzsKCX0KCglyZXR1cm4gMDsKfQovKgpGb3IgdGllCjMKMSAxCjEgMwoxIDIKMiAyCjMgMgoyIDEKMiAzCjMgMwozIDEKICovCgo=