プログラマ専用SNS ミクプラ

atocoderというサイトで８クイーン問題を見つけたので、解いています
問題（http://arc001.contest.atcoder.jp/tasks/arc001_3）
この問題を全探索と再帰関数を使い解を探索し（はじめから与えられている３点は無視してまずはただ単に問題の解を探す）、回答が出たらその答えがはじめに与えられた３点を含むものかどうかを調べて同じなら求める解とすればいいというような考え方でとこうと思いプログラムを書いたのですがうまく動きません。どこがいけないのでしょうか。ご教授お願いします。

コード:

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

typedef long long ll;

char board[10][10]; //ボードの配列を作成
int kimatteru_x[5]; //決まっているQの位置を保存しておく
int kimatteru_y[5]; //決まっているQの位置を保存しておく

//(x, y)におけるかどうかをチェックする関数
bool check(int x, int y){
	//左にないかチェック
	for (int i = 0; i < x; ++i)
	{
		if (board[i][y] == 'Q')
			return false;
	}
	//右はまだない
	//上も下もない
	//下にないかチェック

	int p = x; 
	int q = y;

	//左上にないかチェック
	while(p > 0 && q > 0){
		if (board[--p][--q] == 'Q')
			return false;
	}

	p = x; q = y;
	//左下にないかチェック
	while(p > 0 && q < 7){
		if (board[--p][++q] == 'Q')
			return false;
	}
	return true;
}



bool slove(int x){
	if (x == 8)
	{
		//成功
		//求めた解がはじめに与えられた３点を含んでいる解なのかを求める
		if (board[kimatteru_x[0]][kimatteru_y[0]] == 'Q' && 
			board[kimatteru_x[1]][kimatteru_y[1]] == 'Q' && 
			board[kimatteru_x[2]][kimatteru_y[2]] == 'Q'){
			return true;
		}else{
			return false;
		}
	}

	for (int i = 0; i < 8; ++i)
	{
		if (check(x, i))
		{
			//(x, i)にクイーンがおける場合
			//実際に置いてみる
			board[x][i] = 'Q';
			//次の列やってみる
			if (slove(x + 1)) //次の列以降も成功なら
			{
				return true;
			}else{
				//実際に置いたものを置き直す
				board[x][i] = '.';
			}
		}
	}
	return false; //見つからなければ
}


int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			scanf("%s", &board[j][i]);
			if (board[j][i] == 'Q')
			{
				kimatteru_x[cnt] = j;
				kimatteru_y[cnt] = i;
				cnt++;
			}
		}
	}

	if (slove(0)) //０列目から始めよう
	{

		for (int i = 0; i < 8; ++i)
		{
			for (int j = 0; j < 8; ++j)
			{
				printf("%c", board[j][i]);
			}
			printf("\n");
		}
	}else{
		printf("No Answer\n");
	}

	return 0;
}

入力の読み込み方が間違っているので、うまく入力を保存できないだけでなく範囲外アクセスを起こします。
入力のQを消さずにそのまま処理に使っているため、確かめてはいないですが誤判定の原因になるかもしれません。

みけCAT さんが書きました:

入力の読み込み方が間違っているので、うまく入力を保存できないだけでなく範囲外アクセスを起こします。

入力のQを消さずにそのまま処理に使っているため、確かめてはいないですが誤判定の原因になるかもしれません。

入力が間違っているということなので、以下のようなプログラムを作って試してみました。

コード:

/*
入力の練習
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;


char board[10][10]; //ボードの配列を作成

int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			scanf("%c", &board[j][i]);
		}
	}

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			printf("%c", board[j][i]);
		}
		printf("\n");
	}

	return 0;
}

このコードに入力例
........
........
.......Q
........
..Q.....
........
.Q......
........

を入れると以下のように出力されました

.......
.
......
.Q
.....
...
..Q.
....
...
.....
.Q
......
.

入力をうまく配列に入れれていないことはわかったんですが、どうプログラムを変えれば良いのかわかりません。

hogged さんが書きました:
みけCAT さんが書きました:

入力の読み込み方が間違っているので、うまく入力を保存できないだけでなく範囲外アクセスを起こします。

入力のQを消さずにそのまま処理に使っているため、確かめてはいないですが誤判定の原因になるかもしれません。
入力が間違っているということなので、以下のようなプログラムを作って試してみました。
コード:
/*
入力の練習
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;


char board[10][10]; //ボードの配列を作成

int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			scanf("%c", &board[j][i]);
		}
	}

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			printf("%c", board[j][i]);
		}
		printf("\n");
	}

	return 0;
}
このコードに入力例
........
........
.......Q
........
..Q.....
........
.Q......
........

を入れると以下のように出力されました

.......
.
......
.Q
.....
...
..Q.
....
...
.....
.Q
......
.

入力をうまく配列に入れれていないことはわかったんですが、どうプログラムを変えれば良いのかわかりません。

コード:

/*
入力の練習
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;


char board[10][10]; //ボードの配列を作成
int kimatteru_x[5]; //決まっているQの位置を保存しておく
int kimatteru_y[5]; //決まっているQの位置を保存しておく

int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			scanf("%c", &board[j][i]);
			if (board[j][i] == 'Q')
			{
				kimatteru_x[cnt] = j;
				kimatteru_y[cnt] = i;
				cnt++;
			}
		}
		/*これを入れればいいみたい*/
		getchar();
	}

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			printf("%c", board[j][i]);
		}
		printf("\n");
	}

	return 0;
}

上のように書き換えたら（getchar）、入力例がそのまま出力されるようになりました。
上のようにgetcharを使い、入力表のEOFを飛ばして、配列に入らないようにすれば良いということですか？

hogged さんが書きました:上のようにgetcharを使い、入力表のEOFを飛ばして、配列に入らないようにすれば良いということですか？

いいえ、飛ばすのはEOFではなく改行文字(LF、ASCIIコードなら0x10)です。

みけCAT さんが書きました:
hogged さんが書きました:上のようにgetcharを使い、入力表のEOFを飛ばして、配列に入らないようにすれば良いということですか？
いいえ、飛ばすのはEOFではなく改行文字(LF、ASCIIコードなら0x10)です。

なるほど。char型で文字を受けとっていくと、改行文字も配列に入れてしますので、それを飛ばさないといけないわけですね。
このような表を扱うときに、もうすこしやりやすい方法などないでしょうか？

問題は新しいboardの配列を用意したら解けました。

コード:

/*
深さ優先探索
再帰関数
 はじめから与えられている３点は無視してまずはただ単に問題を解き、回答が出たらその答えが
 ３点を含むものかどうかを調べて同じならok
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
 
typedef long long ll;
 
char board[10][10]; //ボードの配列を作成
int kimatteru_x[5]; //決まっているQの位置を保存しておく
int kimatteru_y[5]; //決まっているQの位置を保存しておく
 
 
//(x, y)におけるかどうかをチェックする関数
bool check(int x, int y){
	//左にないかチェック
	for (int i = 0; i < x; ++i)
	{
		if (board[i][y] == 'Q')
			return false;
	}
	//右はまだない
	//上も下もない
	//下にないかチェック
 
	int p = x; 
	int q = y;
 
	//左上にないかチェック
	while(p > 0 && q > 0){
		if (board[--p][--q] == 'Q')
			return false;
	}
 
	p = x; q = y;
	//左下にないかチェック
	while(p > 0 && q < 7){
		if (board[--p][++q] == 'Q')
			return false;
	}
	return true;
}
 
 
bool slove(int x){
	if (x == 8)
	{
		//成功
		//求めた解がはじめに与えられた３点を含んでいる解なのかを求める
		if (board[kimatteru_x[0]][kimatteru_y[0]] == 'Q' && 
			board[kimatteru_x[1]][kimatteru_y[1]] == 'Q' && 
			board[kimatteru_x[2]][kimatteru_y[2]] == 'Q'){
			return true;
		}else{
			return false;
		}
	}
 
	for (int i = 0; i < 8; ++i)
	{
		if (check(x, i))
		{
			//(x, i)にクイーンがおける場合
			//実際に置いてみる
			board[x][i] = 'Q';
			//次の列やってみる
			if (slove(x + 1)) //次の列以降も成功なら
			{
				return true;
			}else{
				//実際に置いたものを置き直す
				board[x][i] = '.';
			}
		}
	}
	return false; //見つからなければ
}
 
 
int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			scanf("%c", &board[i][j]);
			if (board[i][j] == 'Q')
			{
				kimatteru_x[cnt] = i;
				kimatteru_y[cnt] = j;
				cnt++;
			}
		}
		getchar();
	}
 
	if (slove(0)) //０列目から始めよう
	{
 
		for (int i = 0; i < 8; ++i)
		{
			for (int j = 0; j < 8; ++j)
			{
				printf("%c", board[i][j]);
			}
			printf("\n");
		}
	}else{
		printf("No Answer\n");
	}
 
	return 0;
}

hogged さんが書きました: なるほど。char型で文字を受けとっていくと、改行文字も配列に入れてしますので、それを飛ばさないといけないわけですね。
このような表を扱うときに、もうすこしやりやすい方法などないでしょうか？

C++ なら cin >> でいいのでは？

コード:

int main()
{
    int cnt = 0;
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 'Q') {
                kimatteru_x[cnt] = i;
                kimatteru_y[cnt] = j;
                cnt++;
            }
        }
    if (slove(0))
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j)
                cout << board[i][j];
            cout << endl;
        }
    else
        cout << "No Answer\n";
}

istream::operator>> は改行文字を読み飛ばします。

scanf を使いたいのなら

コード:

    scanf(" %c", &board[i][j]);

%c の前にスペースを入れて、getchar(); を削除する。
このスペースが改行文字を読み飛ばしてくれます。

hogged さんが書きました:このような表を扱うときに、もうすこしやりやすい方法などないでしょうか？

配列の大きさに余裕を持たせて、行を先に処理される添字にすると、1行を1回のscanfで読み込むことができます。

コード:

/*
入力の練習
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;


char board[10][10]; //ボードの配列を作成
int kimatteru_x[5]; //決まっているQの位置を保存しておく
int kimatteru_y[5]; //決まっているQの位置を保存しておく

int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		scanf("%s", board[i]);
		for (int j = 0; j < 8; ++j)
		{
			if (board[i][j] == 'Q')
			{
				kimatteru_y[cnt] = i;
				kimatteru_x[cnt] = j;
				cnt++;
			}
		}
	}

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			printf("%c", board[i][j]);
		}
		printf("\n");
	}

	return 0;
}

みけCAT さんが書きました:
hogged さんが書きました:このような表を扱うときに、もうすこしやりやすい方法などないでしょうか？
配列の大きさに余裕を持たせて、行を先に処理される添字にすると、1行を1回のscanfで読み込むことができます。
コード:
/*
入力の練習
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;


char board[10][10]; //ボードの配列を作成
int kimatteru_x[5]; //決まっているQの位置を保存しておく
int kimatteru_y[5]; //決まっているQの位置を保存しておく

int main(void){
	int cnt = 0;
	//入力
	for (int i = 0; i < 8; ++i)
	{
		scanf("%s", board[i]);
		for (int j = 0; j < 8; ++j)
		{
			if (board[i][j] == 'Q')
			{
				kimatteru_y[cnt] = i;
				kimatteru_x[cnt] = j;
				cnt++;
			}
		}
	}

	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			printf("%c", board[i][j]);
		}
		printf("\n");
	}

	return 0;
}

なるほど、２次元目の配列は１つずつ指定しないで、１次元目の配列だけ指定すればいいわけですね。

追加で質問です
19行めで%sとしているということは、文字列として扱っているということですね？
文字列の場合改行があればそこで、文字列が終了したことになり、次のループに進むということなんですか？

プログラマ専用SNS ミクプラ

8クイーン問題

8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題

Re: 8クイーン問題